Model checking C source code for embedded systems

In this paper, the applicability of model checking to C code for embedded systems is studied. The paper is divided into two parts. In the first part, 13 existing model checkers for C code are detailed and evaluated for their applicability in the verification of C code for embedded systems. A case study is presented that applied CBMC as one representative C code model checker to an exemplary microcontroller program. As a consequence of this case study, we decided to develop a new model checker for source code for microcontrollers, called [mc]square. It is described in the second part of this paper. We present the architecture and the peculiarities of [mc]square, and we successfully applied [mc]square to the same microcontroller program used in the case study.     

基于代码结构信息的软件缺陷定位方法研究

大型软件系统的缺陷定位通常采用源代码与缺陷报告的文本相似性的排序方法,但是这种基于文本相似性的方法没能充分利用源代码结构信息,缺陷定位的准确率低。为了解决这个问题,本文提出了一种基于源代码结构（如类名、方法名、变量名、注释等）信息和历史缺陷报告信息进行缺陷定位的方法,对于源代码结构的不同部分,在与缺陷报告进行词语匹配时,赋予它们不同的权重,同时充分利用历史缺陷报告信息,提高缺陷定位的精度。本文使用了Eclipse作为测试项目进行实验,通过与BugLocator和BugScout等方法的结果进行对比,结果表明本文方法能显著的提高缺陷定位的精度,验证了本文方法的可行性和有效性。     

Software source code sizing using fuzzy logic modeling

Knowing the likely size of a software product before it has been constructed is potentially beneficial in project management: for instance, size can be an important factor in determining an appropriate development/integration schedule, and it can be a significant input in terms of the allocation of personnel and other resources. In this study we consider the applicability of fuzzy logic modeling methods to the task of software source code sizing, using a previously published data set. Our results suggest that, particularly with refinement using data and knowledge, fuzzy predictive models can outperform their traditional regression-based counterparts.     

Assuring property conformance of code generators via model checking

Automatic code generation is an essential cornerstone of today’s model-driven approaches to software engineering. Thus a key requirement for the success of this technique is the reliability and correctness of code generators. This article describes how we employ standard model checking-based verification to check that code generator models developed within our code generation framework Genesys conform to (temporal) properties. Genesys is a graphical framework for the high-level construction of code generators on the basis of an extensible library of well-defined building blocks along the lines of the Extreme Model-Driven Development paradigm. We will illustrate our verification approach by examining complex constraints for code generators, which even span entire model hierarchies. We also show how this leads to a knowledge base of rules for code generators, which we constantly extend by e.g. combining constraints to bigger constraints, or by deriving common patterns from structurally similar constraints. In our experience, the development of code generators with Genesys boils down to re-instantiating patterns or slightly modifying the graphical process model, activities which are strongly supported by verification facilities presented in this article.     

Model driven code checking

Model checkers were originally developed to support the formal verification of high-level design models of distributed system designs. Over the years, they have become unmatched in precision and performance in this domain. Research in model checking has meanwhile moved towards methods that allow us to reason also about implementation level artifacts (e.g., software code) directly, instead of hand-crafted representations of those artifacts. This does not mean that there is no longer a place for the use of high-level models, but it does mean that such models are used in a different way today. In the approach that we describe here, high-level models are used to represent the environment for which the code is to be verified, but not the application itself. The code of the application is now executed as is by the model checker, while using powerful forms of abstraction on-the-fly to build the abstract state space that guides the verification process. This model-driven code checking method allows us to verify implementation level code efficiently for high-level safety and liveness properties. In this paper, we give an overview of the methodology that supports this new paradigm of code verification.     

Software model checking is a rich research field

This introductory paper has been written for readers who know nothing about model checking but do know about software. Its aim is to present, almost without mathematical terms, the fundamental general approaches on which the papers in this Special Section build, and give an idea of what kind of contribution each paper makes. The main issues discussed are motivation for model checking, state spaces, and bounded model checking with sat solvers. Individual papers lead to discuss the following ideas: exploiting a distributed computing environment for model checking, constructing those states first that look most promising for eventually finding errors, only constructing a representative subset of states, the representation of contents of variables in an abstract way with approximation from below, and the use of more general solvers than sat solvers in bounded model checking.     

基于层次单元划分的软件模型检测技术研究

通过对近年来软件模型检测领域流行的几种技术进行综述,提出了一种基于层次单元划分,使用引导式搜索方式的软件模型检测方案。本方案分为预处理、单元划分、状态空间搜索三个阶段,其中使用on-the-fly技术提高了搜索性能。实验证明,该方案在解决状态爆炸问题上有较好的效果。     

基于静态分析技术的源代码安全检测模型*

介绍了当前主流的静态代码分析技术,在分析讨论其优缺点的基础上提出了一种新的静态代码检测模型。该模型结合了当前成熟的静态分析技术,并借鉴了编译器中数据流和控制流分析的思想,获取上下文关联的数据信息,从而更加准确地分析代码中存在的安全问题。     

An analytical model for source code distributability verification简

ne way to speed up the execution of sequential programs is to divide them into concurrent segments and execute such segments in a parallel manner over a distributed computing environment. We argue that the execution speedup primarily depends on the concurrency degree between the identified segments as well as communication overhead between the segments. To guar-antee the best speedup, we have to obtain the maximum possible concurrency degree between the identified segments, taking communication overhead into consideration. Existing code distributor and multi-threading approaches do not fulfill such re-quirements;hence, they cannot provide expected distributability gains in advance. To overcome such limitations, we propose a novel approach for verifying the distributability of sequential object-oriented programs. The proposed approach enables users to see the maximum speedup gains before the actual distributability implementations, as it computes an objective function which is used to measure different distribution values from the same program, taking into consideration both remote and sequential calls. Experimental results showed that the proposed approach successfully determines the distributability of different real-life software applications compared with their real-life sequential and distributed implementations.     

模型检测迷惑二进制恶意代码

对二进制恶意代码进行形式化建模,开发了一个检查迷惑恶意代码的模型检查器。生成迷惑前的二进制恶意代码的有限状态机模型,再使用模型检查器检测迷惑二进制恶意代码,如果迷惑二进制恶意代码能被有限状态机模型识别,可判定其为恶意代码。实验结果表明模型检查迷惑二进制恶意代码是一种有效的静态分析方法,可以检测出一些常用的迷惑恶意代码。     

State-rich model checking

In this paper we survey the area of formal verification techniques, with emphasis on model checking due to its wide acceptance by both academia and industry. The major approaches and their characteristics are presented, together with the main problems faced while trying to apply them. With the increased complexity of systems, as well as interest in software correctness, the demand for more powerful automatic techniques is pushing the theories and tools towards integration. We discuss the state of the art in combining formal methods tools, mainly model checking with theorem proving and abstract interpretation. In particular, we present our own recent contribution on an approach to integrate model checking and theorem proving to handle state-rich systems specified using a combination of Z and CSP.     

Regular model checking

Regular model checking has been studied extensively during recent years as a framework for algorithmic verification of systems with infinite state spaces. We describe the main concepts of the framework, and some of its applications.     

From source code to runtime behaviour: Software metrics help to select the computer architecture

The decision which hardware platform to use for a certain application is an important problem in computer architecture. This paper reports on a study where a data-mining approach is used for this decision. It relies purely on source-code characteristics, to avoid potentially expensive programme executions. One challenge in this context is that one cannot infer how often functions that are part of the application are typically executed. The main insight of this study is twofold: (a) Source-code characteristics are sufficient nevertheless. (b) Linking individual functions with the runtime behaviour of the programme as a whole yields good predictions. In other words, while individual data objects from the training set may be quite inaccurate, the resulting model is not.     

An empirical study of the textual similarity between source code and source code summaries

Source code documentation often contains summaries of source code written by authors. Recently, automatic source code summarization tools have emerged that generate summaries without requiring author intervention. These summaries are designed for readers to be able to understand the high-level concepts of the source code. Unfortunately, there is no agreed upon understanding of what makes up a “good summary.” This paper presents an empirical study examining summaries of source code written by authors, readers, and automatic source code summarization tools. This empirical study examines the textual similarity between source code and summaries of source code using Short Text Semantic Similarity metrics. We found that readers use source code in their summaries more than authors do. Additionally, this study finds that accuracy of a human written summary can be estimated by the textual similarity of that summary to the source code.     

Coherent clusters in source code

This paper presents the results of a large scale empirical study of coherent dependence clusters. All statements in a coherent dependence cluster depend upon the same set of statements and affect the same set of statements; a coherent cluster's statements have ‘coherent’ shared backward and forward dependence. We introduce an approximation to efficiently locate coherent clusters and show that it has a minimum precision of 97.76%. Our empirical study also finds that, despite their tight coherence constraints, coherent dependence clusters are in abundance: 23 of the 30 programs studied have coherent clusters that contain at least 10% of the whole program. Studying patterns of clustering in these programs reveals that most programs contain multiple substantial coherent clusters. A series of subsequent case studies uncover that all clusters of significant size map to a logical functionality and correspond to a program structure. For example, we show that for the program acct, the top five coherent clusters all map to specific, yet otherwise non-obvious, functionality. Cluster visualization also brings out subtle deficiencies in program structure and identifies potential refactoring candidates. A study of inter-cluster dependence is used to highlight how coherent clusters are connected to each other, revealing higher-level structures, which can be used in reverse engineering. Finally, studies are presented to illustrate how clusters are not correlated with program faults as they remain stable during most system evolution.     

Locating features in source code

Understanding the implementation of a certain feature of a system requires identification of the computational units of the system that contribute to this feature. In many cases, the mapping of features to the source code is poorly documented. In this paper, we present a semiautomatic technique that reconstructs the mapping for features that are triggered by the user and exhibit an observable behavior. The mapping is in general not injective; that is, a computational unit may contribute to several features. Our technique allows for the distinction between general and specific computational units with respect to a given set of features. For a set of features, it also identifies jointly and distinctly required computational units. The presented technique combines dynamic and static analyses to rapidly focus on the system's parts that relate to a specific set of features. Dynamic information is gathered based on a set of scenarios invoking the features. Rather than assuming a one-to-one correspondence between features and scenarios as in earlier work, we can now handle scenarios that invoke many features. Furthermore, we show how our method allows incremental exploration of features while preserving the "mental map" the analyst has gained through the analysis.     

Symbolic model checking APSL

Property specification language (PSL) is a specification language which has been accepted as an industrial standard. In PSL, SEREs are used as additional formula constructs. In this paper, we present a variant of PSL, namely APSL, which replaces SEREs with finite automata. APSL and PSL are of the exactly same expressiveness. Then, we extend the LTL symbolic model checking algorithm to that of APSL, and then present a tableau based APSL verification technique, which can be easily implemented via the BDD based symbolic approach. Moreover, we implement an extension of NuSMV, and this adapted version supports symbolic model checking of APSL. Experimental results show that this variant of PSL can be efficiently verified. Henceforth, symbolic model checking PSL can be carried out by a transformation from PSL to APSL and symbolic model checking APSL.     

Symbolic model checking APSL

Property specification language (PSL) is a specification language which has been accepted as an industrial standard. In PSL, SEREs are used as additional formula constructs. In this paper, we present a variant of PSL, namely APSL, which replaces SEREs with finite automata. APSL and PSL are of the exactly same expressiveness. Then, we extend the LTL symbolic model checking algorithm to that of APSL, and then present a tableau based APSL verification technique, which can be easily implemented via the BDD based symbolic approach. Moreover, we implement an extension of NuSMV, and this adapted version supports symbolic model checking of APSL. Experimental results show that this variant of PSL can be efficiently verified. Henceforth, symbolic model checking PSL can be carried out by a transformation from PSL to APSL and symbolic model checking APSL.     

Symmetry and model checking

We show how to exploit symmetry in model checking for concurrent systems containing many identical or isomorphic components. We focus in particular on those composed of many isomorphic processes. In many cases we are able to obtain significant, even exponential, savings in the complexity of model checking.The author's work was supported in part by NSF Grant CCR 941-5496, Semiconductor Research Corporation Contract 95-DP-388, and Texas Advanced Technology Program Grant 003658-250.The author's work was supported in part by NSF Grant CCR-9212183.     

Constraint-based deductive model checking

We show that constraint logic programming (CLP) can serve as a conceptual basis and as a practical implementation platform for the model checking of infinite-state systems. CLP programs are logical formulas (built up from constraints) that have both a logical interpretation and an operational semantics. Our contributions are: (1) a translation of concurrent systems (imperative programs) into CLP programs with the same operational semantics; and (2) a deductive method for verifying safety and liveness properties of the systems which is based on the logical interpretation of the CLP programs produced by the translation. We have implemented the method in a CLP system and verified well-known examples of infinite-state programs over integers, using linear constraints here as opposed to Presburger arithmetic as in previous solutions. Published online: 18 July 2001