Most dynamic program analysis techniques such as profile-driven compiler optimizations, software testing and runtime property checking infer program properties by profiling one or more executions of a program. Unfortunately, program profiling does not come for free. For example, even the most efficient techniques for profiling acyclic, intra-procedural paths can slow down program execution by a factor of 2. In this thesis, we propose techniques that significantly lower the overheads of profiling paths, enabling the use of path-based dynamic analyzes in cost-sensitive environments. Preferential path profiling (PPP) is a novel software-only path profiling scheme that efficiently profiles given subsets of paths, which we refer to as interesting paths. The algorithm is based on the observation that most consumers of path profiles are only interested in profiling a small set of paths known a priori. Our algorithm can be viewed as a generalization of the Ball-Larus path profiling algorithm. Whereas the Ball-Larus algorithm assigns weights to the edges of a given CFG such that the sum of the weights of the edges along each path through the CFG is unique, our algorithm assigns weights to the edges such that the sum of the weights along the edges of interesting paths is unique. Furthermore, our algorithm attempts to achieve a minimal and compact encoding of the interesting paths; such an encoding significantly reduces the overheads of path profiling by eliminating expensive hash operations during profiling. Interestingly, we find that both the Ball-Larus algorithm and PPP are essentially a form of arithmetic coding. We use this connection to prove that the numbering produced by PPP is optimal. We also propose a programmable, non-intrusive hardware path profiler (HPP). The hardware profiler consists of a path detector that detects paths by monitoring the stream of retiring branch instructions emanating from the processor pipeline. The path detector can be programmed to detect various types of paths and track architectural events that occur along paths. The second component of the hardware profiling infrastructure is a Hot Path Table (HPT), that collects accurate hot path profiles. Our experimental evaluation shows that PPP reduces the overheads of profiling paths to 15% on average (with a maximum of 26%). The algorithm can be easily extended to profile inter-procedural paths at minimal additional overheads (average of 26%). We modeled HPP using a cycle-accurate superscalar processor simulator and find that HPP generates accurate path profiles at extremely low overheads (0.6% on average) with a moderate hardware budget. We also evaluated the use of PPP and HPP in a realistic profiling scenarios. We find that the profiles generated by HPP can effectively replace expensive profiles used in profile-driven optimizations. We also find that even well-tested programs tend to exercise a large number of untested paths in the field, emphasizing the need for efficient profiling schemes that can be deployed in production environments.

<p>When exploring a verification approach for Komatsu Forest's control system regarding their forest machines (Valmet), the context of soft real-time systems is illuminated. Because of the nature of such context, the verification process is based on empirical corroboration of requirements fulfillment rather than being a formal proving process.</p><p>After analysis of the literature with respect to the software testing field, two paradigms have been defined in order to highlight important concepts for soft real-time systems. The paradigms are based on an abstract stimuli/response model, which conceptualize a system with inputs and output. Since the system is perceived as a black box, its internal details are hidden and thus focus is placed on a more abstract level.</p><p>The first paradigm, the “input data paradigm”, is concerned about what data to input to the system. The second paradigm, the “input data mechanism paradigm” is concerned about how the data is sent, i.e. the actual input mechanism is focused. By specifying different dimensions associated with each paradigm, it is possible to define their unique characteristics. The advantage of this kind of theoretical construction is that each paradigm creates an unique sub-field with its own problems and techniques.</p><p>The problems defined for this thesis is primarily focused on the input data mechanism paradigm, where devised dimensions are applied. New verification techniques are deduced and analyzed based on general software testing principles. Based on the constructed theory, a test system architecture for the control system is developed. Finally, an implementation is constructed based on the architecture and a practical scenario. Its automation capability is then assessed.</p><p>The practical context for the thesis is a new simulator under development. It is based upon LabVIEW and PXI technology and handles over 200 I/O. Real machine components are connected to the environment, together with artificial components that simulate the engine, hydraulic systems and a forest. Additionally, physical control sticks and buttons are connected to the simulator to enable user testing of the machine being simulated.</p><p>The results associated with the thesis is first of all that usable verification techniques were deduced. Generally speaking, some of these techniques are scalable and are possible to apply for an entire system, while other techniques may be appropriate for selected subsets that needs extra attention. Secondly, an architecture for an automated test system based on a selection of techniques has been constructed for the control system.</p><p>Last but not least, as a result of this, an implementation of a general test system has been possible and successful. The implemented test system is based on both C# and LabVIEW. What remains regarding the implementation is primarily to extend the system to include the full scope of features described in the architecture and to enable result analysis.</p> / <p>Då verifikationstekniker för Komatu Forests styrsystem utreds angående Valmet skogsmaskiner, hamnar det mjuka realtidssystemkontextet i fokus. Ett sådant kontext antyder en process där empirisk styrkning av kravuppfyllande står i centrum framför formella bevisföringsprocesser.</p><p>Efter en genomgång och analys av litteratur för mjukvarutestområdet har två paradigmer definierats med avsikten att belysa viktiga concept för mjuka realtidssystem. Paradigmerna är baserade på en abstrakt stimuli/responsmodell, som beskriver ett system med in- och utdata. Eftersom detta system betraktas som en svart låda är inre detaljer gömda, vilket medför att fokus hamnar på ett mer abstrakt plan.</p><p>Det första paradigmet benämns som “indata-paradigmet” och inriktar sig på vilket data som skickas in i systemet. Det andra paradigmet går under namnet “indatamekanism-paradigmet” och behandlar hur datat skickas in i systemet, dvs fokus placeras på själva inskickarmekanismen. Genom att definiera olika</p><p>dimensioner för de två paradigmen, är det möjligt att beskriva deras utmärkande drag. Fördelen med att använda denna teoretiska konstruktion är att ett paradigm skapar ett eget teoriområde med sina egna frågeställningar och tekniker.</p><p>De problem som definierats för detta arbete är främst fokuserade på indatamekanism-paradigmet, där framtagna dimensioner tillämpas. Nya verifikationstekniker deduceras och analyseras baserat på generella mjukvarutestprinciper. Utifrån den skapade teorin skapas en testsystemarkitektur för kontrollsystemet. Sedan utvecklas ett testsystem baserat på arkitekturen samt ett praktiskt scenario med syftet att utreda systemets automationsgrad.</p><p>Den praktiska miljön för detta arbete kretsar kring en ny simulator under utveckling. Den är baserad på LabVIEW och PXI-teknik och hanterar över 200 I/O. Verkliga maskinkomponenter ansluts till denna miljö tillsammans med konstgjorda komponenter som simulerar motorn, hydralik samt en skog. Utöver detta, ansluts styrspakar och knappar för att möjliggöra användarstyrning av maskinen som simuleras.</p><p>Resultatet förknippat med detta arbete är för det första användbara verifikationstekniker. Man kan generellt säga att några av dessa tekniker är skalbara och därmed möjliga att tillämpa för ett helt system. Andra tekniker är ej skalbara, men lämpliga att applicera på en systemdelmängd som behöver testas mer utförligt.</p><p>För det andra, en arkitektur har konstruerats för kontrollsystemet baserat på ett urval av tekniker. Sist men inte minst, som en följd av ovanstående har en lyckad implementation av ett generellt testsystem utförts. Detta system implementerades med hjälp av C# och LabVIEW. Det som återstår beträffande implementationen är att utöka systemet så att alla funktioner som arkitekturen beskriver är inkluderade samt att införa resultatanalys.</p>

This thesis looks at three aspects related to the design of E-commerce systems, online auctions and distributed grid computing systems. We show how formal verification techniques from computer science can be applied to ensure correctness of system design and implementation at the code level. Through e-ticket sales example, we demonstrate that model checking can locate subtle but critical flaws that traditional control and auditing methods (e.g., penetration testing, analytical procedure) most likely miss. Auditors should understand formal verification methods, enforce engineering to use them to create designs with less of a chance of failure, and even practice formal verification themselves in order to offer credible control and assistance for critical e-systems. Next, we study why many online auctions offer fixed buy prices to understand why sellers and auctioneers voluntarily limit the surplus they can get from an auction. We show when either the seller of the dibbers are risk-averse, a properly chosen fixed permanent buy-price can increase the social surplus and does not decrease the expected utility of the sellers and bidders, and we characterize the unique equilibrium strategies of uniformly risk-averse buyers in a buy-price auction. In the final chapter we look at the design of a distributed grid-computing system. We show how code-instrumentation can be used to generate a witness of program execution, and show how this witness can be used to audit the work of self-interested grid agents. Using a trusted intermediary between grid providers and customers, the audit allows payment to be contingent on the successful audit results, and it creates a verified reputation history of grid providers. We show that enabling the free trade of reputations provides economic incentives to agents to perform the computations assigned, and it induces increasing effort levels as the agents' reputation increases. We show that in such a reputation market only high-type agents would have incentive to purchase a high reputation, and only low-type agents would use low reputations, thus a market works as a natural signaling mechanism about the agents' type. / text

This dissertation attacks the well-known problem of path-imprecision in static program analysis. Our starting point is an existing static program analysis that over-approximates the execution paths of the analyzed program. We then make this over-approximating program analysis more precise for automatic testing in an object-oriented programming language. We achieve this by combining the over-approximating program analysis with usage-observing and under-approximating analyses. More specifically, we make the following contributions. We present a technique to eliminate language-level unsound bug warnings produced by an execution-path-over-approximating analysis for object-oriented programs that is based on the weakest precondition calculus. Our technique post-processes the results of the over-approximating analysis by solving the produced constraint systems and generating and executing concrete test-cases that satisfy the given constraint systems. Only test-cases that confirm the results of the over-approximating static analysis are presented to the user. This technique has the important side-benefit of making the results of a weakest-precondition based static analysis easier to understand for human consumers. We show examples from our experiments that visually demonstrate the difference between hundreds of complicated constraints and a simple corresponding JUnit test-case. Besides eliminating language-level unsound bug warnings, we present an additional technique that also addresses user-level unsound bug warnings. This technique pre-processes the testee with a dynamic analysis that takes advantage of actual user data. It annotates the testee with the knowledge obtained from this pre-processing step and thereby provides guidance for the over-approximating analysis. We also present an improvement to dynamic invariant detection for object-oriented programming languages. Previous approaches do not take behavioral subtyping into account and therefore may produce inconsistent results, which can throw off automated analyses such as the ones we are performing for bug-finding. Finally, we address the problem of unwanted dependencies between test-cases caused by global state. We present two techniques for efficiently re-initializing global state between test-case executions and discuss their trade-offs. We have implemented the above techniques in the JCrasher, Check 'n' Crash, and DSD-Crasher tools and present initial experience in using them for automated bug finding in real-world Java programs.

The use of formal methods in software development seeks to increase our confidence in the resultant system. Their use often requires tool support, so the integrity of a development using formal methods is dependent on the integrity of the tool-set used. Specifically its integrity depends on the theorem prover, since in a typical formal development system the theorem prover is used to establish the validity of the proof obligations incurred by all the steps in the design and refinement process. In this thesis we are concerned with tool-based formal development systems that are used to develop high-integrity software. Since the theorem prover program is a critical part of such a system, it should ideally have been itself formally verified. Unfortunately, most theorem provers are too complex to be verified formally using currently available techniques. An alternative approach, which has many advantages, is to include a proof checker as an extra component in the system, and to certify this. A proof checker is a program which reads and checks the proofs produced by a theorem prover. Proof checkers are inherently simpler than theorem provers, since they only process actual proofs, whereas much of the code of a theorem prover is concerned with searching the space of possible proofs to find the required one. They are also free from all but the simplest user interface concerns, since their input is a proof produced by another program, and their output may be as simple as a `yes/no' reply to the question: Is this a valid proof? plus a list of assumptions on which this judgement is based. When included in a formal development system a stand-alone proof checker is, in one sense, superfluous, since it does not produce any proofs -- the theorem prover does this. Instead its importance is in establishing the integrity of the results of the system -- it provides extra assurance. A proof checker provides extra assurance simply by checking the proofs, since all proofs have then been validated by two independent programs. However a proof checker can provide an extra, and higher, level of assurance if it has been formally verified. In order for formal verification to be feasible the proof checker must be as simple as possible. In turn the simplicity of a proof checker is dependent on the complexity of the data which it processes, that is, the representation of the proofs that it checks. This thesis develops a representation of proofs that is simple and generic. The aim is to produce a generic representation that is applicable to the proofs produced by a variety of theorem provers. Simplicity facilitates verification, while genericity maximises the return on the effort of verification. Using a generic representation places obligations on the theorem provers to produce a proof record in this format. A flexible recorder/translator architecture is proposed which allows proofs to be recorded by existing theorem provers with minimal changes to the original code. The prover is extended with a recorder module whose output is then, if necessary, converted to the generic format by a separate translator program. A formal specification of a checker for proofs recorded in this representation is given. The specification could be used to formally develop a proof-checker, although this step is not taken in this thesis. In addition the characteristics of both the specification and possible implementations are investigated. This is done to assess the size and feasibility of the verification task, and also to confirm that the design is not over-sensitive to the size of proofs. This investigation shows that a checker developed from the specification will be scalable to handle large proofs. To investigate the feasibility of a system based on this architecture, prototype proof recorders were developed for the Ergo 5 and Isabelle 98 theorem provers. In addition a prototype checker was written to check proofs in the proposed format. This prototype is compatible with the formal specification. The combined system was tested successfully using existing proofs for both the Ergo 5 and Isabelle 98 theorem provers.

As software and hardware systems grow more complex and we begin to rely more on their correctness and reliability, it becomes exceedingly important to formally verify certain properties of these systems. If done na&iuml;vely, verifying a system can easily require exponentially more work than running it, in order to account for all possible executions. However, there are often symmetries or other properties of a system that can be exploited to reduce the amount of necessary work. In this thesis, we present a number of approaches that do this in the context of the CSP model checker FDR. CSP is named for Communicating Sequential Processes, or parallel combinations of state machines with synchronised communications. In the FDR model, the component processes are typically converted to explicit state machines while their parallel combination is evaluated lazily during model checking. Our contributions are motivated by this model but applicable to other models as well. We first address the scalability of the component machines by proposing a lazy compiler for a subset of CSP_M selected to model parameterised state machines. This is a typical case where the state space explosion can make model checking impractical, since the size of the state space is exponential in the number and size of the parameters. A lazy approach to evaluating these systems allows only the reachable subset of the state space to be explored. As an example, in studying security protocols, it is common to model an intruder parameterised by knowledge of each of a list of facts; even a relatively small 100 facts results in an intractable 2¹⁰⁰ states, but the rest of the system can ensure that only a small number of these states are reachable. Next, we address the scalability of the overall combination by presenting novel algorithms for bisimulation reduction with respect to strong bisimulation, divergence- respecting delay bisimulation, and divergence-respecting weak bisimulation. Since a parallel composition is related to the Cartesian product of its components, performing a relatively time-consuming bisimulation reduction on the components can reduce its size significantly; an efficient bisimulation algorithm is therefore very desirable. This thesis is motivated by practical implementations, and we discuss an implementation of each of the proposed algorithms in FDR. We thoroughly evaluate their performance and demonstrate their effectiveness.

When exploring a verification approach for Komatsu Forest's control system regarding their forest machines (Valmet), the context of soft real-time systems is illuminated. Because of the nature of such context, the verification process is based on empirical corroboration of requirements fulfillment rather than being a formal proving process. After analysis of the literature with respect to the software testing field, two paradigms have been defined in order to highlight important concepts for soft real-time systems. The paradigms are based on an abstract stimuli/response model, which conceptualize a system with inputs and output. Since the system is perceived as a black box, its internal details are hidden and thus focus is placed on a more abstract level. The first paradigm, the “input data paradigm”, is concerned about what data to input to the system. The second paradigm, the “input data mechanism paradigm” is concerned about how the data is sent, i.e. the actual input mechanism is focused. By specifying different dimensions associated with each paradigm, it is possible to define their unique characteristics. The advantage of this kind of theoretical construction is that each paradigm creates an unique sub-field with its own problems and techniques. The problems defined for this thesis is primarily focused on the input data mechanism paradigm, where devised dimensions are applied. New verification techniques are deduced and analyzed based on general software testing principles. Based on the constructed theory, a test system architecture for the control system is developed. Finally, an implementation is constructed based on the architecture and a practical scenario. Its automation capability is then assessed. The practical context for the thesis is a new simulator under development. It is based upon LabVIEW and PXI technology and handles over 200 I/O. Real machine components are connected to the environment, together with artificial components that simulate the engine, hydraulic systems and a forest. Additionally, physical control sticks and buttons are connected to the simulator to enable user testing of the machine being simulated. The results associated with the thesis is first of all that usable verification techniques were deduced. Generally speaking, some of these techniques are scalable and are possible to apply for an entire system, while other techniques may be appropriate for selected subsets that needs extra attention. Secondly, an architecture for an automated test system based on a selection of techniques has been constructed for the control system. Last but not least, as a result of this, an implementation of a general test system has been possible and successful. The implemented test system is based on both C# and LabVIEW. What remains regarding the implementation is primarily to extend the system to include the full scope of features described in the architecture and to enable result analysis. / Då verifikationstekniker för Komatu Forests styrsystem utreds angående Valmet skogsmaskiner, hamnar det mjuka realtidssystemkontextet i fokus. Ett sådant kontext antyder en process där empirisk styrkning av kravuppfyllande står i centrum framför formella bevisföringsprocesser. Efter en genomgång och analys av litteratur för mjukvarutestområdet har två paradigmer definierats med avsikten att belysa viktiga concept för mjuka realtidssystem. Paradigmerna är baserade på en abstrakt stimuli/responsmodell, som beskriver ett system med in- och utdata. Eftersom detta system betraktas som en svart låda är inre detaljer gömda, vilket medför att fokus hamnar på ett mer abstrakt plan. Det första paradigmet benämns som “indata-paradigmet” och inriktar sig på vilket data som skickas in i systemet. Det andra paradigmet går under namnet “indatamekanism-paradigmet” och behandlar hur datat skickas in i systemet, dvs fokus placeras på själva inskickarmekanismen. Genom att definiera olika dimensioner för de två paradigmen, är det möjligt att beskriva deras utmärkande drag. Fördelen med att använda denna teoretiska konstruktion är att ett paradigm skapar ett eget teoriområde med sina egna frågeställningar och tekniker. De problem som definierats för detta arbete är främst fokuserade på indatamekanism-paradigmet, där framtagna dimensioner tillämpas. Nya verifikationstekniker deduceras och analyseras baserat på generella mjukvarutestprinciper. Utifrån den skapade teorin skapas en testsystemarkitektur för kontrollsystemet. Sedan utvecklas ett testsystem baserat på arkitekturen samt ett praktiskt scenario med syftet att utreda systemets automationsgrad. Den praktiska miljön för detta arbete kretsar kring en ny simulator under utveckling. Den är baserad på LabVIEW och PXI-teknik och hanterar över 200 I/O. Verkliga maskinkomponenter ansluts till denna miljö tillsammans med konstgjorda komponenter som simulerar motorn, hydralik samt en skog. Utöver detta, ansluts styrspakar och knappar för att möjliggöra användarstyrning av maskinen som simuleras. Resultatet förknippat med detta arbete är för det första användbara verifikationstekniker. Man kan generellt säga att några av dessa tekniker är skalbara och därmed möjliga att tillämpa för ett helt system. Andra tekniker är ej skalbara, men lämpliga att applicera på en systemdelmängd som behöver testas mer utförligt. För det andra, en arkitektur har konstruerats för kontrollsystemet baserat på ett urval av tekniker. Sist men inte minst, som en följd av ovanstående har en lyckad implementation av ett generellt testsystem utförts. Detta system implementerades med hjälp av C# och LabVIEW. Det som återstår beträffande implementationen är att utöka systemet så att alla funktioner som arkitekturen beskriver är inkluderade samt att införa resultatanalys.

L’objectif général de cette thèse est le développement de méthodes mathématiques correctes et efficaces en pratique pour prouver automatiquement la correction de logiciels. Plus précisément, cette thèse est fondée sur la théorie de l’interprétation abstraite, un cadre mathématique puissant pour l’approximation du comportement des programmes. En particulier, cette thèse se concentre sur la preuve des propriétés de vivacité des programmes, qui représentent des conditions qui doivent être réalisés ultimement ou de manière répétée pendant l’exécution du programme. La terminaison des programmes est la propriété de vivacité la plus fréquemment considérée. Cette thèse conçoit des nouvelles approximations, afin de déduire automatiquement des conditions suffisantes pour la terminaison des programmes et synthétiser des fonctions de rang définies par morceaux, qui fournissent des bornes supérieures sur le temps d’attente avant la terminaison. Les approximations sont paramétriques dans le choix entre l’expressivité et le coût des approximations sous-jacentes, qui maintiennent des informations sur l’ensemble des valeurs possibles des variables du programme ainsi que les relations numériques possibles entre elles. Cette thèse développe également un cadre d’interprétation abstraite pour prouver des propriétés de vivacité, qui vient comme une généralisation du cadre proposé pour la terminaison. En particulier, le cadre est dédié à des propriétés de vivacité exprimées dans la logique temporelle, qui sont utilisées pour s’assurer qu’un événement souhaitable se produit une fois ou une infinité de fois au cours de l’exécution du programme. Comme pour la terminaison,des fonctions de rang définies par morceaux sont utilisées pour déduire des préconditions suffisantes pour ces propriétés, et fournir des bornes supérieures sur le temps d’attente avant un événement souhaitable. Les résultats présentés dans cette thèse ont été mis en œuvre dans un prototype d’analyseur. Les résultats expérimentaux montrent qu’il donne de bons résultats sur une grande variété de programmes, il est compétitif avec l’état de l’art, et il est capable d’analyser des programmes qui sont hors de la portée des méthodes existantes. / The overall aim of this thesis is the development of mathematically sound and practically efficient methods for automatically proving the correctness of computer software. More specifically, this thesis is grounded in the theory of abstract interpretation, a powerful mathematical framework for approximating the behavior of programs. In particular, this thesis focuses on provingprogram liveness properties, which represent requirements that must be eventually or repeatedly realized during program execution. Program termination is the most prominent liveness property. This thesis designs new program approximations, in order to automatically infer sufficient preconditions for program termination and synthesize so called piecewisedefined ranking functions, which provide upper bounds on the waiting time before termination. The approximations are parametric in the choice between the expressivity and the cost of the underlying approximations, which maintain information about the set of possible values of the program variables along with the possible numerical relationships between them. This thesis also contributes an abstract interpretation framework for proving liveness properties, which comes as a generalization of the framework proposedfor termination. In particular, the framework is dedicated to liveness properties expressed in temporal logic, which are used to ensure that some desirable event happens once or infinitely many times during program execution. As for program termination, piecewise-defined ranking functions are used to infer sufficient preconditions for these properties, and to provide upper boundson the waiting time before a desirable event. The results presented in this thesis have been implemented into a prototype analyzer. Experimental results show that it performs well on a wide variety of benchmarks, it is competitive with the state of the art, and is able to analyze programs that are out of the reach of existing methods.

Contracts for concurrency describe required atomicity of method sequences in concurrent programs. This work proposes a dynamic analyzer to verify programs written in Java against contracts for concurrency. The analyzer was designed to detect violations of parametric contracts with spoilers. The proposed analyzer was implemented as an extension to the RoadRunner framework. Support for accessing the method arguments and return values was added to RoadRunner as a part of the solution. The analyzer was fully implemented and verified on a set of testing programs.

No description available.