Index: /papers/FDL2012/FDL2012.tex =================================================================== --- /papers/FDL2012/FDL2012.tex (revision 82) +++ /papers/FDL2012/FDL2012.tex (revision 83) @@ -33,5 +33,5 @@ - \title{ Compositional System Verification: Exploiting components' verified properties in the abstraction-refinement process} + \title{ An efficient refinement strategy exploiting components' properties in a CEGAR process} \name{Syed Hussein S. ALWI, Emmanuelle ENCRENAZ and C\'{e}cile BRAUNSTEIN} % \thanks{This work was supported by...}} Index: /papers/FDL2012/exp_results.tex =================================================================== --- /papers/FDL2012/exp_results.tex (revision 82) +++ /papers/FDL2012/exp_results.tex (revision 83) @@ -14,8 +14,8 @@ \midrule \midrule - & 1 Master-1 Slave & 308 & 33 442 & 3.64116e+06 & 41.49 \\ - Concrete & 2 Masters-1 Slave & 453 & 140297 & 2.42518e+11 & 1922.75 \\ - Model & 4 Masters-1 Slave & 737 & N/A & N/A & >3days \\ - & 4 Masters-2 Slaves & 911 & N/A & N/A & >3days \\ + & 1 Master-1 Slave & 304 & 7207 & 4.711e+3 & 6.36 \\ + Concrete & 2 Masters-1 Slave & 445 & 24406 & 7.71723e+06 & 35.2 \\ + Model & 4 Masters-1 Slave & 721 & 84118 & 3.17332e+12 & 2818.3 \\ + & 4 Masters-2 Slaves & 911 & N/A & N/A & >1 day \\ \midrule \midrule @@ -48,5 +48,5 @@ \midrule \midrule - Concrete Model & 822 & 140586 & 3.7354e+07 & 294.6 \\ + Concrete Model & 822 & 161730 & 3.7354e+07 & 300.12 \\ \midrule \midrule @@ -75,40 +75,40 @@ \multicolumn{4}{l}{\textbf{\underline{1 Master - 1 Slave :}}} \\ & Prop. Selection & 1 & 2.2 \\ - $\phi_1$ & Incremental & 0 & 18.1 \\ - & Standard MC & - & 14.9 \\ + $\phi_1$ & Incremental & 0 & 6.3 \\ + & Standard MC & - & 6.06 \\ \midrule & Prop. Selection & 0 & 1.0 \\ - $\phi_2$ & Incremental & 467 & 168.0 \\ - & Standard MC & - & 14.9 \\ + $\phi_2$ & Incremental & 562 & 200.9 \\ + & Standard MC & - & 6.13 \\ \midrule \midrule \multicolumn{4}{l}{\textbf{\underline{2 Masters - 1 Slave :}}} \\ & Prop. Selection & 1 & 2.0 \\ - $\phi_1$ & Incremental & 0 & 107.7 \\ - & Standard MC & - & 1181.8 \\ + $\phi_1$ & Incremental & 0 & 20.4 \\ + & Standard MC & - & 37.9 \\ \midrule & Prop. Selection & 0 & 1.0 \\ - $\phi_2$ & Incremental & 0 & 108.5 \\ - & Standard MC & - & 1103.3 \\ + $\phi_2$ & Incremental & 74 & 786.3 \\ + & Standard MC & - & 39.4 \\ \midrule \midrule \multicolumn{4}{l}{\textbf{\underline{4 Masters - 1 Slave :}}} \\ - & Prop. Selection & 1 & 2.1 \\ - $\phi_1$ & Incremental & N/A & >3 days \\ - & Standard MC & - & >3 days \\ + & Prop. Selection & 1 & 2.1 \\ + $\phi_1$ & Incremental & 0 & 261.6 \\ + & Standard MC & - & >1 day \\ \midrule - & Prop. Selection & 0 & 1.0 \\ - $\phi_2$ & Incremental & N/A & >3 days \\ - & Standard MC & - & >3 days \\ + & Prop. Selection & 0 & 1.0 \\ + $\phi_2$ & Incremental & 0 & 263.5 \\ + & Standard MC & - & >1 day \\ \midrule \midrule \multicolumn{4}{l}{\textbf{\underline{4 Masters - 2 Slaves :}}} \\ & Prop. Selection & 1 & 2.2 \\ - $\phi_1$ & Incremental & N/A & >3 days \\ - & Standard MC & - & >3 days \\ + $\phi_1$ & Incremental & N/A & >1 day \\ + & Standard MC & - & >1 day \\ \midrule & Prop. Selection & 0 & 1.1\\ - $\phi_2$ & Incremental & N/A & >3 days \\ - & Standard MC & - & >3 days\\ + $\phi_2$ & Incremental & N/A & >1 day \\ + & Standard MC & - & >1 day\\ \bottomrule \bottomrule @@ -132,10 +132,10 @@ \midrule & Prop. Selection & 0 & 1.02 \\ - $\phi_3$ & Incremental & N/A & N/A \\ - & Standard MC & - & N/A \\ + $\phi_3$ & Incremental & N/A & >1 day \\ + & Standard MC & - & 2645.4 \\ \midrule - & Prop. Selection & 0 & 1.01\\ - $\phi_4$ & Incremental & N/A & N/A \\ - & Standard MC & - & N/A \\ + & Prop. Selection & 0 & 1.01 \\ + $\phi_4$ & Incremental & N/A & >1 day \\ + & Standard MC & - & 1678.1 \\ \bottomrule @@ -147,8 +147,8 @@ -In the following tables: Table \ref{TabVCI_PI} and Table \ref{TabCANBus}, we compare the execution time between our technique (Prop. Selection), incremental\_ctl\_verification (Incremental) and the standard model checking (Standard MC) computed using the \emph{model\_check} command in VIS (Note: Dynamic variable ordering has been enabled with sift method). For the VCI-PI platform, the global property $\phi_1$ is the type $AF((p=1)*AF(q=1))$ and $\phi_2$ is actually a stronger version of the same formula with $AG(AF((p=1)*AF(q=1)))$. We have a total of 42 verifed components properties to be selected in VCI-PI plateform and for the verification of $\phi_1$ we have restrained the selectable properties only to those without AG prefix. In comparison to $\phi_2$, we can see that, a better set of properties available will result in a better abstraction and less refinement iterations. +In the following tables: Table \ref{TabVCI_PI} and Table \ref{TabCANBus}, we compare the execution time between our technique (Prop. Selection), \emph{incremental\_ctl\_verification} (Incremental) and the standard model checking (Standard MC) computed using the \emph{model\_check} command in VIS (Note: Dynamic variable ordering has been enabled with sift method). For the VCI-PI platform, the global property $\phi_1$ is the type $AF((p=1)*AF(q=1))$ and $\phi_2$ is actually a stronger version of the same formula with $AG(AF((p=1)*AF(q=1)))$. We have a total of 42 verifed components properties to be selected in VCI-PI plateform and for the verification of $\phi_1$ we have restrained the selectable properties only to those without AG prefix. In comparison to $\phi_2$, we can see that, a better set of properties available will result in a better abstraction and less refinement iterations. -In the case of the CAN bus platform, the global property $\phi_3$ is the type $AG(((p'=1)*(q'=1)*AF(r_1=1)) -> AF((s_1=1)*AF(t_1=1)))$ and $\phi_4 = AG(((p'=1)*(q'=1)*AG(r_2=0)) -> AG((s_2=0)*(t_2=0)))$. We have at our disposal 103 verified component properties and after the selection process, 3 selected component properties were sufficient to verify both global properties. +In the case of the CAN bus platform, the global property $\phi_3$ is the type $AG(((p'=1)*(q'=1)*AF(r_1=1)) \rightarrow AF((s_1=1)*AF(t_1=1)))$ and $\phi_4 = AG(((p'=1)*(q'=1)*AG(r_2=0)) \rightarrow AG((s_2=0)*(t_2=0)))$. We have at our disposal 103 verified component properties and after the selection process, 3 selected component properties were sufficient to verify both global properties. Globally, we can see that our technique systematically computes faster than the other two methods and interestingly in the case where the size of the platform increases by adding the more connected components, in contrary to the other two methods, our computation time remains stable. Index: /papers/FDL2012/introduction.tex =================================================================== --- /papers/FDL2012/introduction.tex (revision 82) +++ /papers/FDL2012/introduction.tex (revision 83) @@ -22,5 +22,5 @@ -\textbf{\emph{Related Works:}} Xie and Browne have proposed a method for software verification based on composition of several components \cite{XieBrowne03composition_soft}. Their main objective is developing components that could be reused with certitude that their behaviors will always respect their specification when associated in a proper composition. Therefore, temporal properties of the software are specified, verified and packaged with the component for possible reuse. The implementation of this approach on software have been succesful and the application of the assume-guarantee reasoning has considerably reduced the model checking complexity. +\textbf{\emph{Related Works :}} Xie and Browne have proposed a method for software verification based on composition of several components \cite{XieBrowne03composition_soft}. Their main objective is developing components that could be reused with certitude that their behaviors will always respect their specification when associated in a proper composition. Therefore, temporal properties of the software are specified, verified and packaged with the component for possible reuse. The implementation of this approach on software have been succesful and the application of the assume-guarantee reasoning has considerably reduced the model checking complexity. A comprehensive approach to model-check component-based systems with abstraction refinement technique that uses verified properties as abstractions has been presented in \cite{LiSunXieSong08compAbsRef}. @@ -33,5 +33,8 @@ -Recently, an approach based on abstraction refinement technique has been proposed by Kroening and al. to strengthen properties in a finite state system specification \cite{pwk2009-date}. The method, which fundamentally relies on the notion of vacuity, generally produces shorter and stronger properties. In \cite{Kunz_al11ipc_abs}, a method to formally verify low-level software in conjunction with the hardware by exploiting the Interval Property Checking (IPC) with abstraction technique was proposed. This method improves the robustness of interval property checking when proving long global interval properties of embedded systems. +Recently, a CEGAR based technique that combines precise and approximated methods within one abstraction-refinement loop was proposed for software verification \cite{Sharygina_al12PreciseApprox}. This technique uses predicate abstraction and provides a strategy that interleaves approximated abtraction which is fast to compute and precise abstraction which is slow. The result shows a good compromise between the number of refinement iterations and verification time. + + +In \cite{pwk2009-date}, an approach based on abstraction refinement technique has been proposed by Kroening and al. to strengthen properties in a finite state system specification . The method, which fundamentally relies on the notion of vacuity, generally produces shorter and stronger properties. In \cite{Kunz_al11ipc_abs}, a method to formally verify low-level software in conjunction with the hardware by exploiting the Interval Property Checking (IPC) with abstraction technique was proposed. This method improves the robustness of interval property checking when proving long global interval properties of embedded systems. @@ -40,5 +43,6 @@ %\subsection{Contribution} -\textbf{\emph{Contribution :}} We would like to contribute to the improvement of the model-checking technique through the combination of the compositional method and the abstraction-refinement procedure which would allow the verification of complex structured systems and cope with the state space explosion phenomenon. Till now, compositional analysis and abstraction-refinement procedure have been essentially explored seperately, hence the desire to investigate the potential of the combination of these two techniques. The research will lead to a proposal of a development and verification process based on association of several components. In this paper we present a strategy to exploit the properties of verified component in the goal of verifying complex systems with a good initial abstraction and eventually being conclusive in minimal refinement iterations. +\textbf{\emph{Contribution :}} In this paper we present a strategy to exploit the properties of verified component in the goal of verifying complex systems with a good initial abstraction and eventually being conclusive in minimal refinement iterations. We propose a technique to classify component properties according to their pertinency towards the global property, thus, enabling a better selection of properties for the initial abstraction generation. Futhermore, in the case where the verification is not conclusive, we propose a technique guided by the counterexample given by the model-checker to select supplementary properties to improve the abstraction. + In the next section, we will give an overview of our framework and introduce the notations that will be used later. The rest of the paper is organized as follows: section 3 details our strategy of refinement. Section 4 presents the experimentation results and finally, section 5 draws the conclusions and summarize our possible future works. Index: /papers/FDL2012/myBib.bib =================================================================== --- /papers/FDL2012/myBib.bib (revision 82) +++ /papers/FDL2012/myBib.bib (revision 83) @@ -167,9 +167,21 @@ title = "{Verified Systems by Composition from Verified Components} ", booktitle = " In ESEC/FSE 2003: Proceedings of the 11th ACM SIGSOFT Symposium on Foundations of Software Engineering Conference", - pages = {227-286}, + pages = {227-286}, address = "Helsinki, Finland", year = 2003, publisher = "ACM Press" } + + +@conference{ LiSunXieSong08compAbsRef, + author = "J. Li and X. Sun and F. Xie and X. Song", + title = "{Component-Based Abstraction Refinement} ", + booktitle = "In Proc. of 10th International Conference on Software Reuse (ICSR)", + pages = {39-51}, + address = "Beijing, China", + year = 2008, + publisher = "Springer-Verlag" +} + @@ -297,4 +309,14 @@ +@ARTICLE { Sharygina_al12PreciseApprox, + AUTHOR = { Natasha Sharygina and Stefano Tonetta and Aliaksei Tsitovich }, + TITLE = { {An Abstraction Refinement Approach Combining Precise and Approximated Techniques} }, + JOURNAL = { International Journal on Software Tools for Technology Transfer (STTT) }, + VOLUME = {14}, + PAGES ={1-14}, + YEAR = { 2012}, +} + + @conference{ microsoft04SLAM, author = " Thomas Ball and Byron Cook and Vladimir Levin and Sriram K. Rajamani", @@ -324,5 +346,5 @@ YEAR = { 2009 }, PUBLISHER = { ACM }, - PAGES = { 1692--1697 }, + PAGES = { 1692-1697 }, }