Software and Computational Systems Lab

Publications of year 2008

1. Dirk Beyer, Thomas A. Henzinger, and Grégory Théoduloz. Program Analysis with Dynamic Precision Adjustment. In Proceedings of the 23rd IEEE/ACM International Conference on Automated Software Engineering (ASE 2008, L'Aquila, September 15-19), pages 29-38, 2008. IEEE Computer Society Press, Los Alamitos (CA). doi:10.1109/ASE.2008.13 Keyword(s): BLAST, Software Model Checking Publisher's Version PDF Presentation
   Abstract

   We present and evaluate a framework and tool for combining multiple program analyses which allows the dynamic (on-line) adjustment of the precision of each analysis depending on the accumulated results. For example, the explicit tracking of the values of a variable may be switched off in favor of a predicate abstraction when and where the number of different variable values that have been encountered has exceeded a specified threshold. The method is evaluated on verifying the SSH client/server software and shows significant gains compared with predicate abstraction-based model checking.
   BibTeX Entry

   @inproceedings{ASE08, author = {Dirk Beyer and Thomas A.~Henzinger and Gr{\'e}gory Th{\'e}oduloz}, title = {Program Analysis with Dynamic Precision Adjustment}, booktitle = {Proceedings of the 23rd IEEE/ACM International Conference on Automated Software Engineering (ASE~2008, L'Aquila, September 15-19)}, pages = {29-38}, year = {2008}, publisher = {IEEE Computer Society Press, Los Alamitos~(CA)}, isbn = {978-1-4244-2187-9}, doi = {10.1109/ASE.2008.13}, url = {}, pdf = {https://www.sosy-lab.org/research/pub/2008-ASE.Program_Analysis_with_Dynamic_Precision_Adjustment.pdf}, presentation = {https://www.sosy-lab.org/research/prs/2009-04-16_UCB_CPAplus.pdf}, abstract = {We present and evaluate a framework and tool for combining multiple program analyses which allows the dynamic (on-line) adjustment of the precision of each analysis depending on the accumulated results. For example, the explicit tracking of the values of a variable may be switched off in favor of a predicate abstraction when and where the number of different variable values that have been encountered has exceeded a specified threshold. The method is evaluated on verifying the SSH client/server software and shows significant gains compared with predicate abstraction-based model checking.}, keyword = {BLAST,Software Model Checking}, annote = {}, }
2. Dirk Beyer, Damien Zufferey, and Rupak Majumdar. CSIsat: Interpolation for LA+EUF. In A. Gupta and S. Malik, editors, Proceedings of the 20th International Conference on Computer Aided Verification (CAV 2008, Princeton, NY, July 7-14), LNCS 5123, pages 304-308, 2008. Springer-Verlag, Heidelberg. doi:10.1007/978-3-540-70545-1_29 Keyword(s): Software Model Checking Publisher's Version PDF Supplement
   Abstract

   We present CSIsat, an interpolating decision procedure for the quantifier-free theory of rational linear arithmetic and equality with uninterpreted function symbols. Our implementation combines the efficiency of linear programming for solving the arithmetic part with the efficiency of a SAT solver to reason about the boolean structure. We evaluate the efficiency of our tool on benchmarks from software verification. Binaries and the source code of CSIsat are publicly available as free software.
   BibTeX Entry

   @inproceedings{CAV08, author = {Dirk Beyer and Damien Zufferey and Rupak Majumdar}, title = {{{\sc CSIsat}}: Interpolation for {LA+EUF}}, booktitle = {Proceedings of the 20th International Conference on Computer Aided Verification (CAV~2008, Princeton, NY, July 7-14)}, editor = {A.~Gupta and S.~Malik}, pages = {304-308}, year = {2008}, series = {LNCS~5123}, publisher = {Springer-Verlag, Heidelberg}, isbn = {978-3-540-70543-7}, doi = {10.1007/978-3-540-70545-1_29}, sha256 = {5fc10da29ed7a1c90589b1c2080f5b347404b56107364e608b25d10f4b48161f}, url = {http://www.sosy-lab.org/~dbeyer/CSIsat/}, pdf = {https://www.sosy-lab.org/research/pub/2008-CAV.CSIsat_Interpolation_for_LA_EUF.pdf}, abstract = {We present CSIsat, an interpolating decision procedure for the quantifier-free theory of rational linear arithmetic and equality with uninterpreted function symbols. Our implementation combines the efficiency of linear programming for solving the arithmetic part with the efficiency of a SAT solver to reason about the boolean structure. We evaluate the efficiency of our tool on benchmarks from software verification. Binaries and the source code of CSIsat are publicly available as free software.}, keyword = {Software Model Checking}, annote = {}, }
3. Dirk Beyer. CCVisu: Automatic Visual Software Decomposition. In Proceedings of the 30th ACM/IEEE International Conference on Software Engineering (ICSE 2008, Leipzig, May 10-18), pages 967-968, 2008. ACM Press, New York (NY). doi:10.1145/1370175.1370211 Keyword(s): Structural Analysis and Comprehension Publisher's Version PDF Supplement
   Abstract

   Understanding the structure of large existing (and evolving) software systems is a major challenge for software engineers. In reverse engineering, we aim to compute, for a given software system, a decomposition of the system into its subsystems. CCVisu is a lightweight tool that takes as input a software graph model and computes a visual representation of the system's structure, i.e., it structures the system into separated groups of artifacts that are strongly related, and places them in a 2- or 3-dimensional space. Besides the decomposition into subsystems, it reveals the relatedness between the subsystems via interpretable distances. The tool reads a software graph from a simple text file in RSF format, e.g., call, inheritance, containment, or co-change graphs. The resulting system structure is currently either directly presented on the screen, or written to an output file in SVG, VRML, or plain text format. The tool is designed as a reusable software component, easy to use, and easy to integrate into other tools; it is based on efficient algorithms and supports several formats for data interchange.
   BibTeX Entry

   @inproceedings{ICSE08, author = {Dirk Beyer}, title = {{{\sc CCVisu}}: Automatic Visual Software Decomposition}, booktitle = {Proceedings of the 30th ACM/IEEE International Conference on Software Engineering (ICSE~2008, Leipzig, May 10-18)}, pages = {967-968}, year = {2008}, publisher = {ACM Press, New York~(NY)}, isbn = {978-1-60558-079-1}, doi = {10.1145/1370175.1370211}, url = {http://www.sosy-lab.org/~dbeyer/CCVisu/}, pdf = {https://www.sosy-lab.org/research/pub/2008-ICSE.CCVisu_Automatic_Visual_Software_Decomposition.pdf}, abstract = {Understanding the structure of large existing (and evolving) software systems is a major challenge for software engineers. In reverse engineering, we aim to compute, for a given software system, a decomposition of the system into its subsystems. CCVisu is a lightweight tool that takes as input a software graph model and computes a visual representation of the system's structure, i.e., it structures the system into separated groups of artifacts that are strongly related, and places them in a 2- or 3-dimensional space. Besides the decomposition into subsystems, it reveals the relatedness between the subsystems via interpretable distances. The tool reads a software graph from a simple text file in RSF format, e.g., call, inheritance, containment, or co-change graphs. The resulting system structure is currently either directly presented on the screen, or written to an output file in SVG, VRML, or plain text format. The tool is designed as a reusable software component, easy to use, and easy to integrate into other tools; it is based on efficient algorithms and supports several formats for data interchange.}, keyword = {Structural Analysis and Comprehension}, annote = {}, }
4. Faisal Aslam, Christian Schindelhauer, Gidon Ernst, David Spyra, Jan Meyer, and Mohannad Zalloom. Introducing TakaTuka: a Java Virtual Machine for motes. In Proc. of the Embedded Network Sensor Systems (SENSYS), pages 399-400, 2008. ACM. Poster Abstract
   BibTeX Entry

   @inproceedings{ernst:sensys2008, author = {Faisal Aslam and Christian Schindelhauer and Gidon Ernst and David Spyra and Jan Meyer and Mohannad Zalloom}, title = {{Introducing TakaTuka: a Java Virtual Machine for motes}}, booktitle = {Proc. of the Embedded Network Sensor Systems (SENSYS)}, pages = {399--400}, year = {2008}, publisher = {ACM}, note = {Poster Abstract}, }

5. CSIsat: Interpolation for LA+EUF. 2008. Keyword(s): Software Development Project Supplement
   BibTeX Entry

   @misc{CSIsat, title = {{{\sc CSIsat}}: Interpolation for {LA+EUF}}, year = {2008}, url = {http://www.sosy-lab.org/~dbeyer/CSIsat/}, keyword = {Software Development Project}, role = {Contributor and designer}, }