When addressing timing issues in real-time systems, approaches for systematic timing debugging and repair have been missing due to (i) Lack of available feedback: most timing analysis techniques, being closed-form analytical techniques, are unable to provide root cause information when a timing property is violated, which is critical for identifying an appropriate repair, and (ii) Pessimism in the analysis: existing schedulability analysis techniques tend to make worst case assumptions in the presence of non-determinism introduced by real-world factors such as release jitter, or sporadic tasks. To address this gap, we propose an SMT encoding of task runs for exact debugging of timing violations, and a procedure to iteratively repair a given task specification. We demonstrate the utility of this procedure by repairing example task sets scheduled under global non-preemptive earliest-deadline-first scheduling, a common choice for many safety-critical systems.

Abstract PROTON 2.1 presents (1) a new termination checking technique that uses a fine-tuned local LLM to synthesize ranking functions, and (2) support for multiple SAT solvers for non-termination checking.

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 In VeriFuzz 1.4, we implemented two new techniques for checking Non-termination and Termination. VeriFuzz 1.4 won the Termination category of SV-COMP 2023.

Coverage Guided Fuzzing (CGF) is a greybox test generation technique. Bounded Model Checking (BMC) is a whitebox test generation technique. Both these have been highly successful at program coverage as well as error detection. It is well known that CGF fails to cover complex conditionals and deeply nested program points. BMC, on the other hand, fails to scale for programming features such as large loops and arrays. To alleviate the above problems, we propose (1) to combine BMC and CGF by using BMC for a short and potentially incomplete unwinding of a given program to generate effective initial test prefixes, which are then extended into complete test inputs for CGF to fuzz, and (2) in case BMC gets stuck even for the short unwinding, we automatically identify the reason, and rerun BMC with a corresponding remedial strategy. We call this approach as BMCFuzz and implemented it in the VeriFuzz framework. This implementation was experimentally evaluated by participating in Test-Comp 2021 and the results show that BMCFuzz is both effective and efficient at covering branches as well as exposing errors. In this paper, we present the details of BMCFuzz and our analysis of the experimental results.

Abstract We present VeriFuzz 1.2 with two new enhancements: (1) unroll the given program to a short depth and use BMC to produceincompletetest inputs, which are extended intocompleteinputs, and (2) if BMC fails for this short unrolling, automatically identify the reason and rerun BMC with a corresponding remedial strategy.

Unintended non-termination of programs could lead to attacks such as Denial-of-Service(DoS). Current testing techniques are not geared to detect such errors. Towards this, we present FuzzNT, a hybrid testing technique to check non-termination of C programs by combining Coverage Guided Fuzzing (CGF) and abstract interpretation based static analysis. Given a program P and the coverage test inputs generated using CGF, P is transformed into a set of specialized programs, each of which under-approximates P. Abstract interpretation is then used to check each of these smaller programs for non-termination. The key advantage of this approach for checking non-termination is that it reuses the test case corpus created during software development and maintenance. Our preliminary experimental evaluation of FuzzNT shows highly promising results.

A central challenge in designing embedded control systems or cyber-physical systems (CPS) is that of translating high-level models of control algorithms into efficient implementations, while ensuring that model-level semantics are preserved. While a large body of techniques for designing provably correct control strategies exist in the control theory literature, when it comes to transforming mathematical descriptions of these strategies to an efficient implementation, the available means are surprisingly ad hoc in nature. Among other reasons, this is because of (i) implementation platform details not sufficiently being accounted for in controller models, (ii) side effects introduced in the code generation process, (iii) various compiler optimizations whose impact on the dynamics of the plant being controlled not being properly understood, (iv) the presence of analog components on the implementation platform whose behavior is difficult to model, (v) computation and communication delays that exist in an implementation but were not accounted for in the model, and (vi) also the effects of image/video processing whose accuracy and timing behavior are difficult to model. As we move towards designing autonomous systems, these issues become biting problems on the path to certification, and striking a balance between performance and certification. In this position paper, we discuss some of these challenges - that we formulate as the need for modeling the interactions between various implementation layers in a CPS - and potential research directions to address them.

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.

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.

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.

Automotive software applications implement a variety of control algorithms, with many of them being safety-critical in nature. A typical design flow starts with modeling these control algorithms using tools like MATLAB/Simulink. However, at this stage, a number of assumptions, like negligible sensor-to-actuator delay and instantaneous computation of the controller software, are often made. In particular, the details of the software implementation and the computing platform, both eventually defining the timing properties of the applications, are not accounted for. Such idealistic assumptions can cause a significant deviation of the control performance compared to what was proven at the modeling stage. This is usually addressed with multiple design iterations, which are costly and may lead to over-provisioned and thus poorly designed systems. In this paper we attempt to address this problem by proposing a design-and tool flow that integrates software-and platform-level timing information into the high-level modeling stage. We outline our proposed flow using concrete, industry-strength design tools.

IT industry loses tens of billions of dollars annually from security attacks such as malicious reverse engineering. To protect sensitive parts of software from such attacks, we designed a code obfuscation scheme based on nontrivial code clones. While implementing this scheme, we realized that currently there is no framework to assist implementation of such advanced obfuscation techniques. Therefore, we have developed a framework to support code obfuscation using code clones. We could successfully implement our obfuscation technique using this framework in Java. In this paper, we present our framework and illustrate it with an example.