Asynchronous assertions

ABSTRACT

Assertions are a familiar and widely used bug detection technique. Traditional assertion checking, however, is performed synchronously, imposing its full cost on the runtime of the program. As a result, many useful kinds of checks, such as data structure invariants and heap analyses, are impractical because they lead to extreme slowdowns. We present a solution that decouples assertion evaluation from program execution: assertions are checked asynchronously by separate checking threads while the program continues to execute. Our technique guarantees that asynchronous evaluation always produces the same result as synchronous evaluation, even if the program concurrently modifies the program state. The checking threads evaluate each assertion on a consistent snapshot of the program state as it existed at the moment the assertion started.

We implemented our technique in a system called Strobe, which supports asynchronous assertion checking in both single-and multi-threaded Java applications. Strobe runs inside the Java virtual machine and uses copy-on-write to construct snapshots incrementally, on-the-fly. Our system includes all necessary synchronization to support multiple concurrent checking threads, and to prevent data races with the main program threads. We find that asynchronous checking significantly outperforms synchronous checking, incurring tolerable overheads -- in the range of 10% to 50% over no checking at all -- even for heavy-weight assertions that would otherwise result in crushing slowdowns.

References

1. E. Aftandilian and S. Z. Guyer. GC Assertions: Using the Garbage Collector to Check Heap Properties. In ACM Conference on Programming Languages Design and Implementation, pages 235--244, 2009.
2. M. Arnold, M. Vechev, and E. Yahav. QVM: An Efficient Runtime for Detecting Defects in Deployed Systems. In ACM Conference on Object-Oriented Programming Systems, Languages, and Applications, pages 143--162, 2008.
3. A. Aviram, S.-C. Weng, S. Hu, and B. Ford. Efficient System-Enforced Deterministic Parallelism. In Proceedings of the 9th USENIX Conference on Operating Systems Design and Implementation, pages 1--16, 2010.
4. H. Azatchi, Y. Levanoni, H. Paz, and E. Petrank. An On-the-fly Mark and Sweep Garbage Collector Based on Sliding Views. In ACM Conference on Object-Oriented Programming Systems, Languages, and Applications, pages 269--281, 2003.
5. D. F. Bacon, P. Cheng, and V. T. Rajan. A Real-time Garbage Collector with Low Overhead and Consistent Utilization. In ACM Symposium on the Principles of Programming Languages, pages 285--298, 2003.
6. S. Burckhardt, A. Baldassin, and D. Leijen. Concurrent Programming with Revisions and Isolation Types. In ACM Conference on Object-Oriented Programming Systems, Languages, and Applications, pages 691--707, 2010.
7. C. Dimoulas, R. Pucella, and M. Felleisen. Future Contracts. In Proceedings of the 11th ACM SIGPLAN Conference on Principles and Practice of Declarative Programming, pages 195--206, 2009.
8. T. Harris, J. Larus, and R. Rajwar. Transactional Memory, 2nd edition. Morgan and Claypool Publishers, 2010.
9. R. Jones and R. Lins. Garbage Collection. John Wiley and Sons, 1996.
10. K. Kelsey, T. Bai, C. Ding, and C. Zhang. Fast Track: A Software System for Speculative Program Optimization. In International Symposium on Code Generation and Optimization, pages 157--168, 2009.
11. E. B. Nightingale, D. Peek, P. M. Chen, and J. Flinn. Parallelizing security checks on commodity hardware. In ACM Conference on Architectural Support for Programming Languages and Operating Systems, pages 308--318, 2008.
12. C. Reichenbach, N. Immerman, Y. Smaragdakis, E. E. Aftandilian, and S. Z. Guyer. What Can the GC Compute Efficiently?: A Language for Heap Assertions at GC Time. In ACM Conference on Object-Oriented Programming Systems, Languages, and Applications, pages 256--269, 2010.
13. 2007)}shankar07dittoA. Shankar and R. Bodık. DITTO: Automatic Incrementalization of Data Structure Invariant Checks (in Java). In ACM Conference on Programming Languages Design and Implementation, pages 310--319, 2007.
14. 2000 Documentation. Standard Performance Evaluation Corporation, release 1.01 edition, 2001.
15. M. Süsskraut, S. Weigert, U. Schiffel, T. Knauth, M. Nowack, D. B. Brum, and C. Fetzer. Speculation for Parallelizing Runtime Checks. In Proceedings of the 11th International Symposium on Stabilization, Safety, and Security of Distributed Systems, pages 698--710, 2009.
16. M. T. Vechev, E. Yahav, and D. F. Bacon. Correctness-Preserving Derivation of Concurrent Garbage Collection Algorithms. In ACM Conference on Programming Languages Design and Implementation, pages 341--353, 2006.
17. S. Wallace and K. Hazelwood. SuperPin: Parallelizing Dynamic Instrumentation for Real-Time Performance. In International Symposium on Code Generation and Optimization, pages 209--220, 2007.
18. A. Welc, S. Jagannathan, and A. Hosking. Safe futures for Java. In ACM Conference on Object-Oriented Programming Systems, Languages, and Applications, pages 439--453, 2005.
19. T. Yuasa. Real-time garbage collection on general-purpose machines. Journal of Systems and Software, 11 (3): 181--198, 1990.

Index Terms

• Hardware

  • Hardware validation

    • Functional verification

      • Assertion checking

• Software and its engineering

  • Software creation and management

    • Software verification and validation

• Theory of computation

  • Semantics and reasoning

    • Program reasoning

      • Assertions