Smart bounded verification for UML / OCL models

Tweet about this on TwitterShare on FacebookBuffer this pageShare on RedditShare on LinkedInShare on Google+Email this to someone

Checking the correctness of a UML/OCL model is a complex problem and, in general, undecidable. This has forced existing tools for UML/OCL analysis (like our own EMFtoCSP tool) to accept a series of trade-offs: reducing the expressiveness of the modeling language; performing an incomplete search; requiring user guidance to conduct the verification; or, finally, limiting the search space. See a more detailed comparison of all these approaches in this survey.

Bounded veri cation detects faults efficiently but, on the other hand, the absence of faults does not guarantee a correct behavior outside the bounded domain. Hence, choosing suitable bounds is a non-trivial process as there is a trade-off between the veri fication time (faster for smaller domains) and the con fidence in the result (better for larger domains).

Unfortunately, existing tools provide little support for this choice. In this paper (free pdf version), we present a technique that can be used to:

  • automatically infer verification bounds whenever possible,
  • tighten a set of bounds proposed by the user and
  • guide the user in the bound selection process.

This approach may increase the usability of UML/OCL bounded verification tools and improve the efficiency of the verification process.
So, basically, we move from this verification process:

traditional bounded verification

to this one:

smart bounded verification

where our technique suggests potentially good bounds on behalf of the user by means of a series of size abstractions and bound propagations developed for OCL. These bounds can then be passed on the solver for a more efficient process. The following figure tries to describe the whole process in more detail (click on the figure to enlarge)

UML and OCL verification process with smart bounded verification

Typical flow with a bounded verification tool and the role of bound tightening

The computation of the bounds relies on interval constraint propagation techniques. As we explain in the following Section, our approach collects all implicit and explicit constraints from the UML/OCL model and formalizes them as a CSP over a set of variables representing the search space boundaries. As we show in the paper experimental results, tightening bounds does not add a lot of overhead to the whole verification process and has the potential to drastically reduce the time needed to verify the model. This process is not optimal but it is safe, i.e., it may fail to compute the tightest bounds, but it will preserve any witnesses within the original bounds.

As  future  work, we plan to investigate heuristics regarding the best order for selecting bounds, i.e., one that reduces the number of choices and maximizes the amount of information that can be inferred automatically by bound propagation. We also intend to investigate how to reverse this approach, e.g., by broadening (instead of tightening) user provided bounds which are too strict to find a counterexample.

Tweet about this on TwitterShare on FacebookBuffer this pageShare on RedditShare on LinkedInShare on Google+Email this to someone


Your email address will not be published. Required fields are marked *