The Experts below are selected from a list of 81639 Experts worldwide ranked by ideXlab platform
Viktor Kuncak - One of the best experts on this subject based on the ideXlab platform.
-
Software Verification and graph similarity for automated evaluation of students assignments
Information & Software Technology, 2013Co-Authors: Milena Vujosevicjanicic, Mladen Nikolic, Dusan Tosic, Viktor KuncakAbstract:Context: The number of students enrolled in universities at standard and on-line programming courses is rapidly increasing. This calls for automated evaluation of students assignments. Objective: We aim to develop methods and tools for objective and reliable automated grading that can also provide substantial and comprehensible feedback. Our approach targets introductory programming courses, which have a number of specific features and goals. The benefits are twofold: reducing the workload for teachers, and providing helpful feedback to students in the process of learning. Method: For sophisticated automated evaluation of students' programs, our grading framework combines results of three approaches (i) testing, (ii) Software Verification, and (iii) control flow graph similarity measurement. We present our tools for Software Verification and control flow graph similarity measurement, which are publicly available and open source. The tools are based on an intermediate code representation, so they could be applied to a number of programming languages. Results: Empirical evaluation of the proposed grading framework is performed on a corpus of programs written by university students in programming language C within an introductory programming course. Results of the evaluation show that the synergy of proposed approaches improves the quality and precision of automated grading and that automatically generated grades are highly correlated with instructor-assigned grades. Also, the results show that our approach can be trained to adapt to teacher's grading style. Conclusions: In this paper we integrate several techniques for evaluation of student's assignments. The obtained results suggest that the presented tools can find real-world applications in automated grading.
-
Software Verification and graph similarity for automated evaluation of students assignments
arXiv: Artificial Intelligence, 2012Co-Authors: Milena Vujosevicjanicic, Mladen Nikolic, Dusan Tosic, Viktor KuncakAbstract:In this paper we promote introducing Software Verification and control flow graph similarity measurement in automated evaluation of students' programs. We present a new grading framework that merges results obtained by combination of these two approaches with results obtained by automated testing, leading to improved quality and precision of automated grading. These two approaches are also useful in providing a comprehensible feedback that can help students to improve the quality of their programs We also present our corresponding tools that are publicly available and open source. The tools are based on LLVM low-level intermediate code representation, so they could be applied to a number of programming languages. Experimental evaluation of the proposed grading framework is performed on a corpus of university students' programs written in programming language C. Results of the experiments show that automatically generated grades are highly correlated with manually determined grades suggesting that the presented tools can find real-world applications in studying and grading.
Daniel Kroening - One of the best experts on this subject based on the ideXlab platform.
-
Software Verification for weak memory via program transformation
European Symposium on Programming, 2013Co-Authors: Jade Alglave, Daniel Kroening, Vincent Nimal, Michael TautschnigAbstract:Multiprocessors implement weak memory models, but program verifiers often assume Sequential Consistency (SC), and thus may miss bugs due to weak memory. We propose a sound transformation of the program to verify, enabling SC tools to perform Verification w.r.t. weak memory. We present experiments for a broad variety of models (from x86-TSO to Power) and a vast range of Verification tools, quantify the additional cost of the transformation and highlight the cases when we can drastically reduce it. Our benchmarks include work-queue management code from PostgreSQL.
-
Software Verification for weak memory via program transformation
arXiv: Logic in Computer Science, 2012Co-Authors: Jade Alglave, Daniel Kroening, Vincent Nimal, Michael TautschnigAbstract:Despite multiprocessors implementing weak memory models, Verification methods often assume Sequential Consistency (SC), thus may miss bugs due to weak memory. We propose a sound transformation of the program to verify, enabling SC tools to perform Verification w.r.t. weak memory. We present experiments for a broad variety of models (from x86/TSO to Power/ARM) and a vast range of Verification tools, quantify the additional cost of the transformation and highlight the cases when we can drastically reduce it. Our benchmarks include work-queue management code from PostgreSQL.
-
interpolation based Software Verification with wolverine
Computer Aided Verification, 2011Co-Authors: Daniel Kroening, Georg WeissenbacherAbstract:Wolverine is a Software Verification tool using Craig interpolation to compute invariants of ANSI-C and C++ programs. The tool is an implementation of the lazy abstraction approach, generating a reachability tree by unwinding the transition relation of the input program and annotating its nodes with interpolants representing safe states. Wolverine features a built-in interpolating decision procedure for equality logic with uninterpreted functions which provides limited support for bit-vector operations. In addition, it provides an API enabling the integration of other interpolating decision procedures, making it a valuable source of benchmarks and allowing it to take advantage of the continuous performance improvements of SMT solvers. We evaluate the performance of Wolverine by comparing it to the predicate abstraction-based verifier SATABS on a number of Verification conditions of Linux device drivers.
-
a survey of automated techniques for formal Software Verification
IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2008Co-Authors: Vijay Dsilva, Daniel Kroening, Georg WeissenbacherAbstract:The quality and the correctness of Software are often the greatest concern in electronic systems. Formal Verification tools can provide a guarantee that a design is free of specific flaws. This paper surveys algorithms that perform automatic static analysis of Software to detect programming errors or prove their absence. The three techniques considered are static analysis with abstract domains, model checking, and bounded model checking. A short tutorial on these techniques is provided, highlighting their differences when applied to practical problems. This paper also surveys tools implementing these techniques and describes their merits and shortcomings.
-
Craig Interpolation for Quantifier-Free Presburger Arithmetic
2008Co-Authors: Angelo Brillout, Daniel Kroening, Thomas WahlAbstract:Craig interpolation has become a versatile algorithmic tool for improving Software Verification. Interpolants can, for instance, accelerate the convergence of fixpoint computations for infinite-state systems. They also help improve the refinement of iteratively computed lazy abstractions. Efficient interpolation procedures have been presented only for a few theories. In this paper, we introduce a complete interpolation method for the full range of quantifier-free Presburger arithmetic formulas. We propose a novel convex variable projection for integer inequalities and a technique to combine them with equalities. The derivation of the interpolant has complexity low-degree polynomial in the size of the refutation proof and is typically fast in practice
Milena Vujosevicjanicic - One of the best experts on this subject based on the ideXlab platform.
-
Software Verification and graph similarity for automated evaluation of students assignments
Information & Software Technology, 2013Co-Authors: Milena Vujosevicjanicic, Mladen Nikolic, Dusan Tosic, Viktor KuncakAbstract:Context: The number of students enrolled in universities at standard and on-line programming courses is rapidly increasing. This calls for automated evaluation of students assignments. Objective: We aim to develop methods and tools for objective and reliable automated grading that can also provide substantial and comprehensible feedback. Our approach targets introductory programming courses, which have a number of specific features and goals. The benefits are twofold: reducing the workload for teachers, and providing helpful feedback to students in the process of learning. Method: For sophisticated automated evaluation of students' programs, our grading framework combines results of three approaches (i) testing, (ii) Software Verification, and (iii) control flow graph similarity measurement. We present our tools for Software Verification and control flow graph similarity measurement, which are publicly available and open source. The tools are based on an intermediate code representation, so they could be applied to a number of programming languages. Results: Empirical evaluation of the proposed grading framework is performed on a corpus of programs written by university students in programming language C within an introductory programming course. Results of the evaluation show that the synergy of proposed approaches improves the quality and precision of automated grading and that automatically generated grades are highly correlated with instructor-assigned grades. Also, the results show that our approach can be trained to adapt to teacher's grading style. Conclusions: In this paper we integrate several techniques for evaluation of student's assignments. The obtained results suggest that the presented tools can find real-world applications in automated grading.
-
Software Verification and graph similarity for automated evaluation of students assignments
arXiv: Artificial Intelligence, 2012Co-Authors: Milena Vujosevicjanicic, Mladen Nikolic, Dusan Tosic, Viktor KuncakAbstract:In this paper we promote introducing Software Verification and control flow graph similarity measurement in automated evaluation of students' programs. We present a new grading framework that merges results obtained by combination of these two approaches with results obtained by automated testing, leading to improved quality and precision of automated grading. These two approaches are also useful in providing a comprehensible feedback that can help students to improve the quality of their programs We also present our corresponding tools that are publicly available and open source. The tools are based on LLVM low-level intermediate code representation, so they could be applied to a number of programming languages. Experimental evaluation of the proposed grading framework is performed on a corpus of university students' programs written in programming language C. Results of the experiments show that automatically generated grades are highly correlated with manually determined grades suggesting that the presented tools can find real-world applications in studying and grading.
Dirk Beyer - One of the best experts on this subject based on the ideXlab platform.
-
domain independent interprocedural program analysis using block abstraction memoization
Foundations of Software Engineering, 2020Co-Authors: Dirk Beyer, Karlheinz FriedbergerAbstract:Whenever a new Software-Verification technique is developed, additional effort is necessary to extend the new program analysis to an interprocedural one, such that it supports recursive procedures. We would like to reduce that additional effort. Our contribution is an approach to extend an existing analysis in a modular and domain-independent way to an interprocedural analysis without large changes: We present interprocedural block-abstraction memoization (BAM), which is a technique for procedure summarization to analyze (recursive) procedures. For recursive programs, a fix-point algorithm terminates the recursion if every procedure is sufficiently unrolled and summarized to cover the abstract state space. BAM Interprocedural works for data-flow analysis and for model checking, and is independent from the underlying abstract domain. To witness that our interprocedural analysis is generic and configurable, we defined and evaluated the approach for three completely different abstract domains: predicate abstraction, explicit values, and intervals. The interprocedural BAM-based analysis is implemented in the open-source Verification framework CPAchecker. The evaluation shows that the overhead for modularity and domain-independence is not prohibitively large and the analysis is still competitive with other state-of-the-art Software-Verification tools.
-
Software Verification in the google app engine cloud
Computer Aided Verification, 2014Co-Authors: Dirk Beyer, Georg Dresler, Philipp WendlerAbstract:Software Verification often requires a large amount of computing resources. In the last years, cloud services emerged as an inexpensive, flexible, and energy-efficient source of computing power. We have investigated if such cloud resources can be used effectively for Verification. We chose the platform-as-a-service offer Google App Engine and ported the open-source Verification framework CPAchecker to it. We provide our new Verification service as a web front-end to users who wish to solve single Verification tasks (tutorial usage), and an API for integrating the service into existing Verification infrastructures (massively parallel bulk usage). We experimentally evaluate the effectiveness of this service and show that it can be successfully used to offload Verification work to the cloud, considerably sparing local Verification resources.
-
R.: “Software Model Checking via Large-Block Encoding”. In: FMCAD’09
2009Co-Authors: Dirk Beyer, Ro Cimatti, Alberto Griggio, Erkan M. Keremoglu, Roberto SebastianiAbstract:Abstract—The construction and analysis of an abstract reach-ability tree (ART) are the basis for a successful method for Software Verification. The ART represents unwindings of the control-flow graph of the program. Traditionally, a transition of the ART represents a single block of the program, and therefore, we call this approach single-block encoding (SBE). SBE may result in a huge number of program paths to be explored, which constitutes a fundamental source of inefficiency. We propose a generalization of the approach, in which transitions of the ART represent larger portions of the program; we call this approach large-block encoding (LBE). LBE may reduce the number of paths to be explored up to exponentially. Within this framework, we also investigate symbolic representations: for representing abstract states, in addition to conjunctions as used in SBE, we investigate the use of arbitrary Boolean formulas; for computing abstract-successor states, in addition to Cartesian predicate abstraction as used in SBE, we investigate the use of Boolean predicate abstraction. The new encoding leverages the efficiency of state-of-the-art SMT solvers, which can symbolically compute abstract large-block successors. Our experiments on benchmark C programs show that the large-block encoding outperforms the single-block encoding. Software model checking is an effective technique for Software Verification. Several advances in the field have lead to tool
-
configurable Software Verification concretizing the convergence of model checking and program analysis
Computer Aided Verification, 2007Co-Authors: Dirk Beyer, Thomas A Henzinger, Gregory TheodulozAbstract:In automatic Software Verification, we have observed a theoretical convergence of model checking and program analysis. In practice, however, model checkers are still mostly concerned with precision, e.g., the removal of spurious counterexamples; for this purpose they build and refine reachability trees. Lattice-based program analyzers, on the other hand, are primarily concerned with efficiency. We designed an algorithm and built a tool that can be configured to perform not only a purely tree-based or a purely lattice-based analysis, but offers many intermediate settings that have not been evaluated before. The algorithm and tool take one or more abstract interpreters, such as a predicate abstraction and a shape analysis, and configure their execution and interaction using several parameters. Our experiments show that such customization may lead to dramatic improvements in the precision-efficiency spectrum.
-
the blast query language for Software Verification
Static Analysis Symposium, 2004Co-Authors: Dirk Beyer, Thomas A Henzinger, Adam Chlipala, Ranjit Jhala, Rupak MajumdarAbstract:Blast is an automatic Verification tool for checking temporal safety properties of C programs. Blast is based on lazy predicate abstraction driven by interpolation-based predicate discovery. In this paper, we present the Blast specification language. The language specifies program properties at two levels of precision. At the lower level, monitor automata are used to specify temporal safety properties of program executions (traces). At the higher level, relational reachability queries over program locations are used to combine lower-level trace properties. The two-level specification language can be used to break down a Verification task into several independent calls of the model-checking engine. In this way, each call to the model checker may have to analyze only part of the program, or part of the specification, and may thus succeed in a reduction of the number of predicates needed for the analysis. In addition, the two-level specification language provides a means for structuring and maintaining specifications.
Natasha Sharygina - One of the best experts on this subject based on the ideXlab platform.
-
hifrog smt based function summarization for Software Verification
Tools and Algorithms for Construction and Analysis of Systems, 2017Co-Authors: Leonardo Alt, Sepideh Asadi, Hana Chockler, Karine Even Mendoza, Grigory Fedyukovich, Antti E J Hyvarinen, Natasha SharyginaAbstract:Function summarization can be used as a means of incremental Verification based on the structure of the program. HiFrog is a fully featured function-summarization-based model checker that uses SMT as the modeling and summarization language. The tool supports three encoding precisions through SMT: uninterpreted functions, linear real arithmetics, and propositional logic. In addition the tool allows optimized traversal of reachability properties, counter-example-guided summary refinement, summary compression, and user-provided summaries. We describe the use of the tool through the description of its architecture and a rich set of features. The description is complemented by an experimental evaluation on the practical impact the different SMT precisions have on model-checking.
-
periplo a framework for producing effective interpolants in sat based Software Verification
International Conference on Logic Programming, 2013Co-Authors: Simone Fulvio Rollini, Antti E J Hyvarinen, Grigory Fedyukovich, Natasha SharyginaAbstract:Propositional interpolation is widely used as a means of overapproximation to achieve efficient SAT-based symbolic model checking. Different Verification applications exploit interpolants for different purposes; it is unlikely that a single interpolation procedure could provide interpolants fit for all cases. This paper describes the PeRIPLO framework, an interpolating SAT-solver that implements a set of techniques to generate and manipulate interpolants for different model checking tasks. We demonstrate the flexibility of the framework in two Software bounded model checking applications: Verification of a given source code incrementally with respect to various properties, and Verification of Software upgrades with respect to a fixed set of properties. Both applications use interpolation for generating function summaries. Our systematic experimental investigation shows that size and logical strength of interpolants significantly affect Verification, that these characteristics depend on the role played by interpolants, and that therefore techniques for tuning size and strength can be used to customize interpolants in different applications.
-
VCEGAR: Verilog counterexample guided abstraction refinement
2007Co-Authors: Himanshu Jain, Daniel Kroening, Natasha Sharygina, Edmund ClarkeAbstract:Abstract. As first step, most model checkers used in the hardware industry convert a high-level register transfer language (RTL) design into a netlist. However, algorithms that operate at the netlist level are unable to exploit the structure of the higher abstraction levels, and thus, are less scalable. The RTL level of a hardware description language such as Verilog is similar to a Software program with special features for hardware design such as bit-vector arithmetic and concurrency. We describe a hardware model checking tool, VCEGAR, which performs Verification at the RTL level using Software Verification techniques. It implements predicate abstraction and a refinement loop as used in Software Verification. The novel aspects are the generation of new word-level predicates, an efficient predicate image computation in presence of a large number of predicates, and precise modeling of the bit-vector semantics of hardware designs.
-
cogent accurate theorem proving for program Verification
Computer Aided Verification, 2005Co-Authors: Byron Cook, Daniel Kroening, Natasha SharyginaAbstract:Many symbolic Software Verification engines such as Slam and ESC/Java rely on automatic theorem provers. The existing theorem provers, such as Simplify, lack precise support for important programming language constructs such as pointers, structures and unions. This paper describes a theorem prover, Cogent, that accurately supports all ANSI-C expressions. The prover's implementation is based on a machine-level interpretation of expressions into propositional logic, and supports finite machine-level variables, bit operations, structures, unions, references, pointers and pointer arithmetic. When used by Slam during the model checking of over 300 benchmarks, Cogent's improved accuracy reduced the number of Slam timeouts by half, increased the number of true errors found, and decreased the number of false errors.
