Data poisoning is a training-time attack that undermines the trustworthiness of learned models. In a targeted data poisoning attack, an adversary manipulates the training dataset to alter the classification of a targeted test point. Given the typically large size of training dataset, manual detection of poisoning is difficult. An alternative is to automatically measure a dataset's robustness against such an attack, which is the focus of this paper. We consider a threat model wherein an adversary can only perturb the labels of the training dataset, with knowledge limited to the hypothesis space of the victim's model. In this setting, we prove that finding the robustness is an NP-Complete problem, even when hypotheses are linear classifiers. To overcome this, we present a technique that finds lower and upper bounds of robustness. Our implementation of the technique computes these bounds efficiently in practice for many publicly available datasets. We experimentally demonstrate the effectiveness of our approach. Specifically, a poisoning exceeding the identified robustness bounds significantly impacts test point classification. We are also able to compute these bounds in many more cases where state-of-the-art techniques fail.

Verification tools and techniques are known to possess strengths and weaknesses with respect to different program syntax and semantics. Thus in practice, a sequence of verification techniques is often custom built to verify a class of similar programs. Such a sequence of techniques is called a strategy. So far, verification strategies have been created manually or through machine learning methods. Manual methods of strategy creation are expensive. They create few strategies from which a suitable one is selected for a given program based on its class. The program's class is identified by observing the status of a few manually defined boolean program features. On the other hand, machine learning methods rely on a relatively large set of complex features such as program construct counts, ratios of construct counts or program graphs. In this paper we utilize a machine learning approach to create strategies. This approach combines the strengths of both previously known methods. It uses boolean program features with machine learning to predict verification strategies. Further, we introduce novel program features termed as relative boolean metrics that are boolean abstractions of ratios of construct counts. We implement the novel methods in a tool, extensively evaluate it on a large set of diverse academic benchmarks, and use it to verify four industrial applications. On an average our tool leads the state of the art manual and machine learning-based strategy prediction methods by 11% in terms of the number of properties it successfully verified.

Abstract PROTON is a tool to check whether a given C program has a non-terminating behaviour or not. It is built around the C Bounded Model Checker (CBMC). CBMC cannot prove non-termination directly, as all non-terminating runs are unbounded. PROTON annotates the loops in a given program with assertions that check for a recurrent program state. Violation of such an assertion shows the existence of a recurrent state and thereby proves non-termination. PROTON also transforms the violating trace returned by CBMC into a non-termination witness for the program.

Abstract Precondition inferenceis an important problem with many applications. Existing precondition inference techniques for programs with arrays have limited ability to find and prove the weakest preconditions, especially when programs have non-determinism. In this paper, we propose an approach to overcome the limitation. As the problem is uncomputable in general, our approach targets a special class of programs called linear array programs that are commonly encountered in practical applications and have been studied before. We also focus on a class of quantified formulas for pre- and postconditions that suffice to specify program properties in many applications. Our approach uses two novel techniques calledStructural Array Abduction(SAA) andSpecialized Maximality Checking(SMC). SAA is an abduction-based technique used to infer quantified preconditions and necessary inductive invariants. SMC proves that an inferred precondition is the weakest by finding an under-approximated program and solving the complement verification problem on it using SAA. When inconclusive, it attempts to weaken the precondition. Our approach can infer (and also prove) the weakest preconditions for a range of benchmarks relatively quickly, and outperforms competing techniques.

Abstract We present VeriAbsL, a reachability verifier that performs verification in three stages. First, it slices the input code using a combination of two slicers, then it verifies the slices using predicted strategies, and at last, it composes the result of verifying the individual slices. We introduce a novel shallow slicing technique that uses variable reference information of the program, and data and control dependencies of the entry function to generate slices. We also introduce a novel strategy prediction technique that uses machine learning to predict a strategy. It uses boolean features to describe a program to a neural network that predicts a strategy. We use the portfolio of VeriAbs, a reachabiltiy verifier with manually defined strategies. In sv-comp 2023, VeriAbsL verified 227 (Without witness validation.) more programs than VeriAbs, and 475 (Without witness validation.) programs that VeriAbs could not verify.

Heating, ventilation, and air-conditioning (HVAC) system’s supervisory control is crucial for energy-efficient thermal comfort in buildings. The control logic is usually specified as ‘if-then-that-else’ rules that capture the domain expertise of HVAC operators, but they often have conflicts that may lead to sub-optimal HVAC performance. We propose EImprove, a reinforcement-learning (RL) based framework that exploits these conflicts to learn a resolution policy. We evaluate EImprove through a co-simulation strategy involving EnergyPlus simulations of a real-world office setting and a formal requirement specifier. Our experiments show that EImprove learns 75% faster than a pure RL framework.

Static analysis tools, being scalable, are widely used to detect runtime errors in industry strength software. However, the downside is that these tools generate a large number of false alarms which considerably reduces their effectiveness in detecting the real bugs and fixing them. This shortcoming becomes more pronounced in analysis of evolving software where false alarms reported in an earlier version are re-reported while analysing subsequent versions. Ideally, developers would not like to see the re-reporting of old alarms that are inconsequential to the changes made. To address this problem, static analyzers have been enhanced with techniques like syntactic masking, and several heuristics to decide if an old alarm should be reported again or not. Naturally, however, as they do not take semantics of change into consideration, they are either unsound, or still end up reporting a large number of old alarms. This paper proposes a change-based alarm reporting approach, that reports an alarm only if the alarm point lies on a newly introduced, potentially unsafe, execution path. For this, we intro-duce a novel and effective semantic-aware change-impact analysis (CIA), that helps in detecting presence of such execution paths. In order to make this efficient, especially for development processes involving frequent code commits, our technique incrementally builds the required dataflow analyses and program dependence information. Our experiments, on 124 versions of a core banking application, demonstrate that the proposed approach is i) 66% faster than whole program analysis, ii) leads to 83% reduction in repetitive alarms, and iii) reports 62% lesser alarms as compared to syntactic CIA.

Abstract VeriAbs is a strategy selection-based reachability verifier for C programs. The selection of a suitable strategy is from a pre-defined set of strategies and by taking into account the syntax and semantics of the code to be verified. This year we present VeriAbs version 1.4.1 in which a novel preprocessor to strategy selection is introduced. The preprocessor checks for the feasibility of performing a lightweight slicing of the input code using function call graph and variable reference information. By this if the program is found to besliceable, sub-programs or slices are generated, and the known strategy selection algorithm of VeriAbs is applied to each slice. The verification results of each slice are then composed to derive that of the entire program. This compositional verification has improved the scalability of VeriAbs and presented in this paper.

Conventional automated test case generation techniques do not scale to modern software systems, as these systems have a large number of requirements that change frequently. In this paper, we present a scalable algorithm, AGenT, that generates test cases to cover maximal requirements. AGenT takes Expressive Decision Tables (EDT), specifying requirements of a system, as input and realises these as multiple Discrete Time Automata (DTAs). AGenT then generates test cases to cover each row of the tables. To improve scalability, it attempts to cover nearer rows (requiring fewer inputs) first, where distance is measured using a novel distance-to-match heuristic. It also maintains information about desirability and predictability of inputs so as to select promising inputs with a higher probability. Although the algorithm has been presented in the context of EDT, it operates on its DTA representation and hence can be applied to any system that is represented as a collection of DTAs like Statemate and Stateflow. In this paper, we describe AGenT in detail and present findings from two experiments that we conducted. We compared AGenT with state-of-the-art algorithms, DRAFT and a random test case generation algorithm, RTG. In the first experiment, AGenT took a maximum of 144 seconds to cover all rows whereas the other two algorithms timed out on many modules. In the second experiment, for a module with 701 rows, AGenT achieved 7% more coverage than DRAFT and 12% more than RTG.

Abstract VeriAbs is a strategy selection based reachability verifier for C code. It analyzes the structure of loops, and intervals of inputs to choose one of the four verification strategies implemented in VeriAbs. In this paper, we present VeriAbs version 1.4 with updates in three strategies. We add an array verification technique called full-program induction, and enhance the existing techniques of loop pruning, k-path interval analysis, and disjunctive loop summarization. These changes have improved the verification of programs with arrays, and unstructured loops and unstructured control flows.

Verification of programs continues to be a challenge and no single known technique succeeds on all programs. In this paper we present VeriAbs, a reachability verifier for C programs that incorporates a portfolio of techniques implemented as four strategies, where each strategy is a set of techniques applied in a specific sequence. It selects a strategy based on the kind of loops in the program. We analysed the effectiveness of the implemented strategies on the 3831 verification tasks from the ReachSafety category of the 8th International Competition on Software Verification (SV-COMP) 2019 and found that although classic techniques - explicit state model checking and bounded model checking, succeed on a majority of the programs, a wide range of further techniques are required to analyse the rest. A screencast of the tool is available at https://youtu.be/Hzh3PPiODwk.

One of the main difficulties in estimating the Worst Case Execution Time (WCET) at the binary level is that machine instructions do not allow inferring call contexts as precisely as source code, since compiler optimizations obfuscate control flow and type information. On the other hand, WCET estimation at source code level can be precise in tracking call contexts, but it is pessimistic for functions that are not available as source code.

VeriFuzz is a program aware fuzz testing tool, which combines the power of feedback-driven evolutionary fuzz testing with static analysis. VeriFuzz deploys lightweight static analysis to extract meaningful information about program behavior that can aid fuzzing based test-input generation to achieve coverage goals quickly. We use constraint-solver to generate an initial population of test-inputs. VeriFuzz could generate the maximum number of counterexamples for reachsafety category benchmarks in SV-COMP 2019 and in Test-Comp 2019 [ 16 ]. (All the terms in typewriter font are competition specific. See [ 15 ].)

The problem of schedulability analysis, i.e., determining whether a given task set meets its deadline constraints, has been extensively studied in the real-time systems literature. However, if a task set is not schedulable, then the schedulability analysis results using known techniques (such as utilization-based tests) offer little insight into which task parameters could be changed or refined, in order to make the task set schedulable. To address this problem, we encode the schedulability analysis problem as an equivalent model checking problem. By analyzing the counterexamples reported by the model checker, we discover subsets of values of task parameters that lead to timing violations. We propose a procedure that iteratively refines the task specification by rejecting these subsets, thereby converging towards schedulability. We believe that this approach would be useful for timing debugging of real-time systems, which has received relatively less attention in the literature, especially given its practical relevance.

Loop Abstraction followed by Bounded Model Checking, or LABMC in short, is a promising recent technique for proving safety of large programs. In an experimental setup proposed last year [14], LABMC was combined with slicing and Iterative Context Extension (ICE) with the aim of achieving scalability over industrial code. In this paper, we address two major limitations of that set-up, namely (i) the inability of ICE to prune redundant code in a verification context, and (ii) the unavailability of a tool that implements the set-up. We propose an improvement over ICE called Iterative Function Level Slicing (IFLS) and incorporate it in our tool called ELABMC, to offer an efficient implementation of [14]. We substantiate our claim with two sets of experiments over industrial applications as well as academic benchmarks. Quantifying the benefits of IFLS over traditional ICE in one, our results report that IFLS leads to 34.9% increase in efficiency, 17.7% improvement in precision, and scales in 14.2% more cases. With the second experiment, we show that ELABMC outperforms state-of-the-art verification techniques in the task of identifying static analysis warnings as false alarms.

The application of Model Checking to compute WCET has not been explored as much as Integer Linear Programming (ILP), primarily because model checkers fail to scale for complex programs. These programs have loops with large or unknown bounds, leading to a state space explosion that model checkers cannot handle. To overcome this, we have developed a technique, TIC, that employs slicing, loop acceleration and over-approximation on time-annotated source code, enabling Model Checking to scale better for WCET computation. Further, our approach is parametric, so that the user can make a trade-off between the tightness of WCET estimate and the analysis time. We conducted experiments on the Mälardalen benchmarks to evaluate the effect of various abstractions on the WCET estimate and analysis time. Additionally, we compared our estimates to those made by an ILP-based analyzer and found that our estimates were tighter for more than 30% of the examples and were equal for the rest.

Creating test cases to cover all functional requirements of real-world systems is hard, even for domain experts. Any method to generate functional test cases must have three attributes: (a) an easy-to-use formal notation to specify requirements, from a practitioner's point of view, (b) a scalable test-generation algorithm, and (c) coverage criteria that map to requirements. In this paper we present a method that has all these attributes. First, it includes Expressive Decision Table (EDT), a requirement specification notation designed to reduce translation efforts. Second, it implements a novel scalable row-guided random algorithm with fuzzing (RGRaF)(pronounced R-graph) to generate test cases. Finally, it implements two new coverage criteria targeted at requirements and requirement interactions. To evaluate our method, we conducted experiments on three real-world applications. In these experiments, RGRaF achieved better coverage than pure random test case generation. When compared with manual approach, our test cases subsumed all manual test cases and achieved up to 60% effort savings. More importantly, our test cases, when run on code, uncovered a bug in a post-production sub-system and captured three missing requirements in another.

Requirements of reactive systems express the relationship between sensors and actuators and are usually described in a natural language and a mix of state-based and stream-based paradigms. Translating these into a formal language is an important pre-requisite to automate the verification of requirements. The analysis effort required for the translation is a prime hurdle to formalization gaining acceptance among software engineers and testers. We present Expressive Decision Tables (EDT), a novel formal notation designed to reduce the translation efforts from both state-based and stream-based informal requirements. We have also built a tool, EDTTool, to generate test data and expected output from EDT specifications. In a case study consisting of more than 200 informal requirements of a real-life automotive application, translation of the informal requirements into EDT needed 43% lesser time than their translation into Statecharts. Further, we tested the Statecharts using test data generated by EDTTool from the corresponding EDT specifications. This testing detected one bug in a mature feature and exposed several missing requirements in another. The paper presents the EDT notation, comparison to other similar notations and the details of the case study.

Model checking engines employed to generate test cases covering the structure of the model or code are limited by factors like code size, loops and floating point computation. We propose an approach that overcomes these limitations by approximating code fragments by dynamically inferring their post-conditions. We use Daikon to infer likely invariants from execution traces, which are used as postconditions to compactly represent the state space computed by these code fragments. The resulting approximation enables application-level test case generation over larger code sizes using model checking, given the same resources of time, memory and computing power. Case studies show the efficacy of this approach.

Static analysis of code is very effective in finding common programmer errors but it comes at a price - a large number of false positives. Model checking, on the other hand, is very precise but does not scale up. We have developed a tool that combines both techniques and also implements a novel loop abstraction. The tool was run on 2 million lines of embedded code to analyze for two properties - division by zero and array index out of bounds. In other experiments we compared the precision of our tool to that achieved by tools implementing abstract interpretation. This paper presents details of the tool and the results of evaluations that we have carried out to measure the scalability and to compare the precision of our method on industry code against other static analysis tools.

Visual notations like class diagrams, and use case diagrams are very popular with practitioners for capturing requirements of software applications. These notations unfortunately have little or no semantics, and hence cannot be analyzed by tools. Formal notations, on the other hand, have associated tools that check specifications for stated properties but are difficult to integrate with software development processes in use. Strengths of both approaches can be exploited by giving formal semantics to popular notations. Here we propose a novel usage of UML object diagrams for specifying pre- and post-conditions for use cases and capturing global system properties as class invariants. A translation is defined from object diagrams to the formal notation TLA/sup +/. The TLA/sup +/ specification is then formally verified using the model checker TLC. The proposed notation is intuitive, expressive and formal. We present a small case study to illustrate its strengths.