• Không có kết quả nào được tìm thấy

Computer Aided Verification

N/A
N/A
Nguyễn Gia Hào

Academic year: 2023

Chia sẻ "Computer Aided Verification"

Copied!
234
0
0

Loading.... (view fulltext now)

Văn bản

Sriram Sankaranarayanan University of Colorado, Boulder, USA Koushik Sen University of California, Berkeley, USA Sanjit A. Sorawee Porncharoenwase University of Washington, USA Mathias Preiner Stanford University, USA Talia Ringer University of Washington, USA.

1 Introduction

Register automata (RA) support infinite alphabets by allowing input characters to be stored in registers during computation and compared to existing values ​​that are already stored in registers [17]. In this paper, we combine the best features of these two models—first-order alphabet theories and registers—into a new model, symbolic register automata (SRA).

2 Motivating Example

For example, an RA can define the language of all lists of integers in which all numbers appearing in even positions are the same. Register automata (RA) and their variants can store characters in registers during computation and compare characters with values ​​already stored in registers [17].

3 Symbolic Register Automata

For example, transition out of state 1 reads each character and stores it in registerr1. For example, transition out of state 2 can only be caused by the same character that was stored in 1 when reading the transition out state - that is, the first characters in the product codes must be the same.

4 Decidability Properties

In fact, register equalities determine whether (i) register constraints of an outgoing transition are satisfied; (ii) how many elements of the queue do we need for the transition to occur, analogous to condition 2 of Lemma 1. Given any SRA, we can use the notion of register abstraction to construct an equivalent normalized SRA, where (i) says keep track of how the domains of registers change with transitions, (ii) transitions are obtained by breaking up the one of the original SRA into minterms and discarding the ones disabled according to Lemma 1 .

5 Evaluation

Succinctness of SRAs vs SFAs

In cases where the register values ​​span small sets (eg [0-9]) it is often possible to build an SFA corresponding to the SRA, but the construction always results in very large automata. To answer question 1, even for finite alphabets, it is not possible to compile SRAs into SFAs.

Performance of Membership Checking

The performance of SRA (ie Java) is not particularly affected by the size of the expression. As expected, for SRAs the time required to check membership increases linearly with input size (axes are log scale).

Fig. 2. Experimental results.
Fig. 2. Experimental results.

Performance of Decision Procedures

6 Conclusions

SEFAs allow arbitrary k-ary predicates over input theory, resulting in most problems being undecidable (e.g. equivalence and empty intersections) and the model not closing under Boolean operations. We also plan to actively study automata learning for SRAs, building on techniques for SFAs [1], RAs [6,8,16] and nominal automata [19].

In [31] the authors apply the idea of ​​trace extraction refinement to timed automata where a finite automaton is maintained to exclude unfeasible edge sequences. The CEGAR approach was also recently used in the LinAIG framework for verifying linear hybrid automata [1].

2 Timed Automata and Zones

Timed Automata

In [21,22], the authors provide an algorithm where these boundaries are dynamically adjusted during exploration, allowing coarser abstractions to be obtained. The abstractions consist of increasing the size of don't-cares to reduce the number of linear predicates used in the representation.

Zones and DBMs

A valuation v satisfies a guard g, denoted v |= g, if all atomic guards are true when each x ∈ C is replaced by v(x). A temporal automaton A is a tuple (L,Inv, 0,C, E), where L is a finite set of locations, Inv:L → ΦC defines location invariants, C is a finite set of clocks, E⊆ L × ΦC×2C × List a set of edges, and0∈ List the initial location.

Clock-Predicate Abstraction and Interpolation

3 Enumerative Algorithm

Enumerative algorithm checking the reacha-

  • Abstract Forward Reachability: AbsReach
  • Refinement: Refine

Thus, the algorithm uses a possibly different abstract domain for each node in the exploration tree. In the rest of this paper, we will use the following heuristic: we perform a cut on the first node ni0..nj0, which is covered by some other node.

Fig. 2. Spurious counter-example: Z 1 ∩ C 1 = ∅
Fig. 2. Spurious counter-example: Z 1 ∩ C 1 = ∅

4 Symbolic Algorithm

  • Boolean Encoding of Zones
  • Reduction and Successor Computation
  • Model-Checking Algorithm
  • Abstraction Refinement

We show how each basic operation on zones can be computed in our BDD encoding. Note that the algorithm can be easily extended to the general case; but it simplifies the presentation.

5 Experiments

Single-process scheduling analysis. In this version, one process sequentially executes tasks on one machine, and the execution time of each cycle depends on the state of the process. This depends on the semantics of the process, as the binding depends on the reachable states.

Fig. 3. Comparison of our enumerative and symbolic algorithms (referred to as Abs- Abs-enumerative and Abs-symbolic) with Uppaal and PAT
Fig. 3. Comparison of our enumerative and symbolic algorithms (referred to as Abs- Abs-enumerative and Abs-symbolic) with Uppaal and PAT

6 Conclusion and Future Work

Our contributions. The aim of this paper is to come up with fast algorithms for dealing with diagonal constraints. Finite solution for state-based guard equations. The smallest solution of the equations of definition 9 can be obtained by a standard Kleene iteration for computing fixed points.

Table 1. Experiments: the column #D gives the number of diagonal constraints. Four methods have been reported in the table
Table 1. Experiments: the column #D gives the number of diagonal constraints. Four methods have been reported in the table

Automata for Discounted-Sum Inclusion

While these algorithms outperform other existing approaches for DS capture at runtime [15,17], even these do not scale well on weighted automata with more than a few hundred states [11]. Consequently, DS comparators reduce DS containment to language containment between (non-deterministic) B¨uchi automata.

2 Preliminaries and Related Work

The decidability of the DS inclusion is an open problem when the discount factor >1 is arbitrary. These limitations also appear in the theoretical complexity and practical performance of DS inclusion.

3 DS-inclusion with Integer Discount-Factor

DS-comparison Languages and Their Safety/Co-safety Properties

The central result of this section is that DS comparison languages ​​are safety or cosafety languages ​​for all (integer and non-integer) discount factors (Theorem 1). Due to duality of safety/cosafety languages, it is sufficient to show that DS comparison language with ≤ is a safety language.

Deterministic DS-comparator for Integer Discount-Factor This section issues deterministic safety/co-safety constructions for DS-

Then, the transition relation for DFA can mimic the inductive definition of recoverable space, i.e. a proof similar to Lemma1 proves an upper bound for the generative space of very good prefixes of Aμ,d≤: Lemma 2.

Quantitative Inclusion with Safety/Co-safety Comparators This section investigates quantitative language inclusion with regular safety/co-

Finally, since DS comparators are regular safety/co-safety automata (Corollary1), apply Theorem 4 to obtain an algorithm for DS inclusion that uses regular safety/co-safety comparators (Corollary5). Let P, Q be weighted automata, and C be a regular safety/co-safety DS comparator with integer discount factor d > 1.

4 Implementation and Experimental Evaluation

A similar argument proves non-strict DS inclusion reduces to emptiness of a weak-B¨uchi automaton[27] of size |P||C||Q| ·2O(|Q|·|C|) (see Appendix). Let P, Q be weighted automata, and C be a regular (co)safety DS comparator with integer discount factor d >1. The complexity of DS inclusion is|P||C||Q| ·2O(|Q|·|C|).

Fig. 1. s P = s Q on x -axis, wt = 4, δ = 3, d = 3, P ⊂ Q
Fig. 1. s P = s Q on x -axis, wt = 4, δ = 3, d = 3, P ⊂ Q

5 Concluding Remarks

Our technique is able to calculate a feasible repair for 91% of the errors detected by UPPAAL in the generated mutants. If the MaxSMT instance allows a solution, the resulting model provides values ​​of the model variables.

Fig. 1. TDT represented as a sequence diagram with timing annotationsVarious changes to the underlying NTA
Fig. 1. TDT represented as a sequence diagram with timing annotationsVarious changes to the underlying NTA

2 Preliminaries

The transmission time of the message is controlled by the clock variablex and can vary between 1 and 2 time units. The processing time indbServer is limited to exactly 1 time unit by the location immutability<=1 and the transition wait>=1.

3 Logical Encoding of Timed Diagnostic Traces

This is achieved by the location invariant x<=2 on the reqReceivedLocation indb together with the transition security x>=1 on the transition from reqReceived to qProcess. To illustrate the coding, consider the transition Θ3 of the TDT in Example 1 that corresponds to the transition from state (reqSent, reqProcessing) to state (serReceiving,reqAwaiting) during the clock sense reset of the NTA of Fig.2.

Fig. 2. Network of timed automata - running example
Fig. 2. Network of timed automata - running example

4 Repair

The purpose of the bound variation analysis is to provide hints to the system designer about what minimal syntactic changes to the considered model can prevent violation of propertyΠ. We implement this analysis by using the bound variational TDT constraint systemTbv to derive an instance of the partial MaxSMT problem whose solutions provide candidate repairs to the timed automaton.

5 Admissibility of Repair

As a consequence, only a subset of states inS in the untimed construction proposed in [3] can be included in F. It requires a construction of the untimed B¨uchi automata using the approach of [3], and subsequently a language equivalence test of the untimed languages ​​accepted by the untimed BAs using, for example, the automata-theoretic constructions proposed in [9].

6 Case Studies and Experimental Evaluation

Two repairs reduce the maximum time delay between two ventricular or ventricular heartbeats of the patient. The impact of the number of clock constraints and clock variables on the computation costs can be seen, for example, in the data for the pacemaker and FDDI models.

Fig. 3. Control loop of T AR T AR
Fig. 3. Control loop of T AR T AR

7 Conclusion

Complexity of model checking formulas with one quan- tifier alternation [18]). The model checking problem for HyperLTL formulas

While avoiding the complexity problem, this transformation requires in-depth knowledge of the system, is prone to errors, and cannot be automatically verified because the problem of checking implications becomes undecidable [11]. In the next section, we present a technique that circumvents the complexity problem while still inheriting strong correctness guarantees.

3 Model Checking with Quantifier Alternations

Model Checking with Given Strategies

The model checking problem for HyperLTL formulas with one quantifier alternation and given strategies for the existential quantifiers is in PSPACE in the size of the formula and NLOGSPACE in the size of the product of the strategy and the system. It is easy to see that the original specification implies the modified specification, since the original formula is the conclusion of the implication.

Model Checking with Synthesized Strategies

In the event that the constraint system is satisfiable, we can extract interpretations for the functions μ and l∃. Given that ≥0, if the constraint system is satisfiable for some bound on the size of Sk, then Sk is A.

4 Synthesis with Quantifier Alternations

A universal co-B¨uchi automaton A and an ak-lookahead transitive system Sk.SkA are given if and only if the running graph Sk× A is admissible.

5 Implementations and Experimental Evaluation

Comparing these results with the performance of symmetry property approximations [18], we again observe that the verification times are similar. Our evaluation is based on two families of comparisons, the dining cryptograph problem [5] and a simplified version of the symmetry problem in mutual exclusion protocols discussed earlier.

Table 1. Experimental results for MCHyper on the software doping and mutual exclu- exclu-sion benchmarks
Table 1. Experimental results for MCHyper on the software doping and mutual exclu- exclu-sion benchmarks

Side Channels

We show that the deterministic variant of the Shannon mitigation problem is persistent and propose a dynamic programming algorithm to approximate the optimal solution to the problem by sifting through a limited number of solutions. We show that Schmitis is scalable in synthesizing mitigation policies within seconds and significantly improves the security (entropy) of the applications. b) The timing functions for each secret value of the program.

2 Overview

These entropies are defined in Section 3 and measure the residual entropy of the secret set after the observations. The observations x1 and x2 stand for all observations of C2−C5 and of C8−C9, resp.; (b) Leaning discriminant decision tree (middle): it characterizes the functional groups of Fig.1(b) with internals of the program in Fig.1(a); and (c) observations (right) after the smoothing by Schmit results in two classes of observations.

Fig. 2. (a) Mitigation policy calculation with deterministic algorithm (left). The obser- obser-vations x 1 and x 2 stands for all observations from C 2 −C 5 and from C 8 −C 9 , resp.; (b) Leaned discriminant decision tree (center): it characterizes the fu
Fig. 2. (a) Mitigation policy calculation with deterministic algorithm (left). The obser- obser-vations x 1 and x 2 stands for all observations from C 2 −C 5 and from C 8 −C 9 , resp.; (b) Leaned discriminant decision tree (center): it characterizes the fu

3 Preliminaries

4 Shannon Mitigation Problem

We note that the above definitions do not represent the expected entropies, but rather entropies corresponding to the expected cluster sizes. The expected incentive associated with a policy μ, π(μ), is defined as the probabilistic weighted sum of the penalties, i.e.

5 Algorithms for Shannon Mitigation Problem

Deterministic Shannon Mitigation

It is straightforward to verify that an instance of the resulting min-guess entropy problem has a yes answer if and only if the two-way partitioning instance does. The algorithm terminates as soon as the solution of the current step respects the performance bound.

Stochastic Shannon Mitigation Algorithm

The objective function of the optimization problem is defined based on the entropy criteria from E. Finally, the min-guess entropy optimization problem is an example of mixed integer programming [32].

6 Implementation Details

Figure 4(b,c) shows two instances of mitigation policies that are possible for stochastic mitigation. For stochastic optimization with min-guess entropy, we code the problem in Gurobi [19] as a mixed integer programming (MIP) problem [32].

7 Case Study

Security: Stochastic and deterministic variants improve min-guess entropy 89 times under the given performance overhead. For the stochastic algorithm, the policy results in 2 clusters and the min-guess entropy is improved to 500.5.

Fig. 6. Initial functional observations, decision tree, and the mitigated observations from left to right for Gabfeed, Jetty, and Verbal Expressions from top to bottom.
Fig. 6. Initial functional observations, decision tree, and the mitigated observations from left to right for Gabfeed, Jetty, and Verbal Expressions from top to bottom.

8 Related Work

ACM (2000)

Next, we define the assembly function inference problem together with an inductive invariant for checking the safety of the assembled program, where both are restricted to the given language. 2The proofs of the claims in this paper can be found in the extended version [29].

Fig. 1. Constant-time insert to an array.
Fig. 1. Constant-time insert to an array.

3 Inferring Self Compositions for Restricted Languages of Inductive Invariants

Semantic Self Composition

To ensure that the function is well-defined, we require that( . MCM)≡true, which ensures that the everyone-state satisfies at least one of the conditions. Together, these requirements ensure that the conditions induce a splitting of the set of allk-states.

The Problem of Inferring Self Composition with Inductive Invariant Lemma 1 states the soundness of the reduction of k-safety to ordinary safety. Together

Therefore, we consider the self-composition function and the inductive invariant together, as a pair, which leads to the following definition. Since the reachable states of Tf are determined by {CM}M (which define f), this reveals the interplay between the self-composition function and the inductive invariant.

4 Algorithm for Inferring Composition-Invariant Pairs

Instead, the abstract counterexample obtained in violation of the conditions must be eliminated by modifying f. If there exists an invariant pair of composition (f,Inv), then there also exists a kuf(ˆsm)=f(ˆsm).

5 Evaluation and Conclusion

While the latter is not required, it also does not limit the generality of the approach (since the language we consider is closed under Boolean operations). In: Proceedings of the 38th ACM SIGPLAN Conference on Design and Implementation of Programming Languages, PLDI 2017, Barcelona, ​​Spain, June.

Table 1. Examples that require semantic compositions
Table 1. Examples that require semantic compositions

Delayed-Action Games

The omission of private variables enables the use of off-the-shelf tools to implement and analyze DAG-based models. Moreover, we propose a DAG-based framework for strategy synthesis and analysis of security-aware systems.

2 Stochastic Games

Because the UAV is unaware of the attack, it believes it is entering zone C, when the true new location due to the attack is (NE). The rule H4 specifies that a PLII attempt θ to reveal the true value can succeed with probability pi where PLII belief is updated (i.e., u=t), and otherwise remains unchanged.

Fig. 1. The UAV belief (solid square) vs. the true value (solid diamond) of its location.
Fig. 1. The UAV belief (solid square) vs. the true value (solid diamond) of its location.

Hình ảnh

Fig. 2. Experimental results.
Fig. 2. Spurious counter-example: Z 1 ∩ C 1 = ∅
Fig. 3. Comparison of our enumerative and symbolic algorithms (referred to as Abs- Abs-enumerative and Abs-symbolic) with Uppaal and PAT
Table 1. Experiments: the column #D gives the number of diagonal constraints. Four methods have been reported in the table
+7

Tài liệu tham khảo

Tài liệu liên quan

In Basic English Lexicology, compounding (or words –composition) is the building of a new word by joining two or more words. It is clear that the components of a compound