An Empirical Study of Software Metrics

Software metrics are computed for the purpose of evaluating certain characteristics of the software developed. A Fortran static source code analyzer, FORTRANAL, was developed to study 31 metrics, including a new hybrid metric introduced in this paper, and applied to a database of 255 programs, all of which were student assignments. Comparisons among these metrics are performed. Their cross-correlation confirms the internal consistency of some of these metrics which belong to the same class. To remedy the incompleteness of most of these metrics, the proposed metric incorporates context sensitivity to structural attributes extracted from a flow graph. It is also concluded that many volume metrics have similar performance while some control metrics surprisingly correlate well with typical volume metrics in the test samples used. A flexible class of hybrid metric can incorporate both volume and control attributes in assessing software complexity.     

A rigorous approach towards test case generation

This paper presents a method to generate test cases for sequential programs and concurrent programs written in a flow based program language. Test cases of sequential programs are generated based on condition calculation, and can be combined together to form SYN-sequences for concurrent program testing. Semantics of the language provides an infrastructure for the test case generation, and thus our method may be considered as a rigorous and systematic approach to the program testing. Compared with some formal testing methods, our method can avoid hitting state explosion problem in the test formation. Besides, the complexity analysis reveals that our method is time saving. Our method has been applied to generate test cases for PPP over ATM, a subsystem of IAD that runs data and voice over DSL.     

A Measure of Control Flow Complexity in Program Text

This paper discusses the need for measures of complexity and unstructuredness of programs. A simple language independent concept is put forward as a measure of control flow complexity in program text and is then developed for use as a measure of unstructuredness. The proposed metric is compared with other metrics, the most notable of which is the cyclomatic complexity measure. Some experience with automatic tools for obtaining these metrics is reported.     

基于符号执行和N-scope复杂度的代码混淆度量方法

代码混淆可有效对抗逆向工程等各类MATE攻击威胁,作为攻击缓和性质的内生安全技术发展较为成熟,对代码混淆效果的合理度量具有重要价值。代码混淆度量研究相对较少,针对代码混淆弹性的度量方法与泛化性、实用性度量方法相对缺乏。符号执行技术广泛应用于反混淆攻击,其生成遍历程序完整路径输入测试集的难度可为混淆弹性度量提供参考,然而基于程序嵌套结构的对抗技术可显著降低符号执行效率,增加其混淆弹性参考误差。针对上述问题,提出结合符号执行技术和N-scope复杂度的代码混淆度量方法,该方法首先基于程序符号执行时间定义程序混淆弹性;其次提出适配符号执行的N-scope复杂度,定义程序混淆强度同时增强符号执行对多层嵌套结构程序的混淆弹性度量鲁棒性;进而提出结合动态分析与静态分析的混淆效果关联性分析,通过对程序进行符号执行与控制流图提取量化混淆效果。面向C程序构建了该度量方法的一种实现框架并验证,实验对3个公开程序集及其混淆后程序集约4 000个程序进行混淆效果度量,度量结果表明,提出的度量方法在较好地刻画混淆效果的同时拥有一定的泛化能力与实用价值;模拟真实混淆应用场景给出了该度量方法的使用样例,为混淆技术使...     

Structural testing of concurrent programs

Although structural testing techniques are among the weakest available with regard to developing confidence in sequential programs, they are not without merit. The authors extend the notion of structural testing criteria to concurrent programs and propose a hierarchy of supporting structural testing techniques. Coverage criteria described include concurrency state coverage, state transition coverage and synchronization coverage. Requisite support tools include a static concurrency analyzer and either a program transformation system or a powerful run-time monitor. Also helpful is a controllable run-time scheduler. The techniques proposed are suitable for Ada or CSP-like languages. Best results are obtained for programs having only static naming of tasking objects     

BB图的枚举特征

在并发程序复杂性度量研究中,我们曾定义了一种B图,用以作为Ada并发程序中一种会合关系的模型。我们将B图推广到BB图。n节点BB图是在n个节点的串联树上再添加若干条边,其约束条件是：每个节点的入度不大于二,每个节点的出度也不大于二。给出BB图的若干若干枚举特征,指出同第二类Stiding数的密切关系。     

Advanced chopping of sequential and concurrent programs

A chop for a source statement s and a target statement t reveals the program parts involved in conveying effects from s to t. While precise chopping algorithms for sequential programs are known, no chopping algorithm for concurrent programs has been reported at all. This work introduces six chopping algorithms for concurrent programs, which offer different degrees of precision, ranging from imprecise over context-sensitive to time-sensitive. Our evaluation on concurrent Java programs shows that context-sensitive and time-sensitive chopping reduces chop sizes significantly. We further present an extensive evaluation of chopping algorithms for sequential programs and describe a new, easy-to-implement chopping technique for sequential programs that computes fast and almost context-sensitive chops.     

Concurrent programming in VISO

Concurrent programming is more difficult to use and understand than sequential programming. In order to simplify this type of programming a number of approaches have been developed such as visual programming. Visual Occam (VISO) is a visual programming language for concurrent programming. It has a graphical syntax based on the language Occam and its semantics is represented both in petri net and process calculus. This paper presents a modular visual approach to write concurrent programs using the VISO language. Concurrent programs in VISO are specified graphically at different levels of abstraction. This paper describes this modular visual approach by constructing two examples in VISO. The first example is a simple concurrent program and it is mainly used to show the details of constructing a concurrent program in VISO. The second example is a larger concurrent program with more levels of abstraction. Copyright © 2000 John Wiley & Sons, Ltd.     

并行程序Petri网模型的结构性质

正确性是并行程序的基础,但是由于它的复杂性,其验证要比串行程序困难得多,因此有必要进行建模并研究其性质.从程序的角度出发,在将基于消息传递的并行程序转换为Petri网模型之后,证明了与并行正确的并行程序对应的Petri网模型应当满足的结构性质,包括强连通性、S-不变量、T-不变量、受控死锁性质以及守恒性,并举例说明了这些性质在并行程序验证中的应用.这些性质可用于并行程序的事前验证,而且避免了使用动态性质进行验证时的状态爆炸问题,从而提高并行程序设计和验证效率.同时这些方法具有良好的可推广性.     

A systematic review of approaches for testing concurrent programs

Concurrent programs are replacing the sequential programs as they utilize the true capabilities of multicore architecture. The extensive use of multicore systems and multithreaded paradigms warrants more attention to the testing of the concurrent programs. The testing concurrent program is not a new field as it has been more than 40 years because the first problem related to the testing concurrent program was addressed by the researchers. The field covers various domains, which include concurrency problems, testing approaches, techniques, graphical representations, tools, and subject systems. This paper aims at providing an overview of research in the domain of testing concurrent programs by classifying it into eight categories: (a) reachability testing, (b) structural testing, (c) model‐based testing, (d) mutation‐based testing, (e) slicing‐based testing, (f) formal methods, (g) random testing, and (h) search‐based testing. The survey is focused on the techniques applied, methodologies followed, and tools used in these aforementioned approaches. Furthermore, the gaps are also identified in different approaches. The paper concludes with the consolidation of various testing parameters along with the future directions. Copyright © 2015 John Wiley & Sons, Ltd.     

Relational interprocedural verification of concurrent programs

We propose a general analysis method for recursive, concurrent programs that track effectively procedure calls and return in a concurrent context, even in the presence of unbounded recursion and infinite-state variables like integers. This method generalizes the relational interprocedural analysis of sequential programs to the concurrent case, and extends it to backward or coreachability analysis. We implemented it for programs with scalar variables and experimented with several classical synchronization protocols in order to illustrate the precision of our technique and also to analyze the approximations it performs.     

A formal semantics for debugging synchronous message passing-based concurrent programs

In this paper, we propose a semantic framework to debug synchronous message passing-based con- current programs, which are increasingly useful as parallel computing and distributed systems become more and more pervasive. We first design a concurrent programming language model to uniformly represent exist- ing concurrent programming languages. Compared to sequential programming languages, this model contains communication statements, i.e., sending and receiving statements, and a concurrent structure to represent com- munication and concurrency. We then propose a debugging process consisting of a tracing and a locating procedure. The tracing procedure re-executes a program with a failed test case and uses specially designed data structures to collect useful execution information for locating bugs. We provide for the tracing procedure a struc- tural operational semantics to represent synchronous communication and concurrency. The locating procedure backward locates the ill-designed statement by using information obtained in the tracing procedure, generates a fix equation, and tries to fix the bug by solving the fix equation. We also propose a structural operational semantics for the locating procedure. We supply two examples to test our proposed operational semantics.     

Beyond contracts for concurrency

SCOOP is a concurrent programming language with a new semantics for contracts that applies equally well in concurrent and sequential contexts. SCOOP eliminates race conditions and atomicity violations by construction. However, it is still vulnerable to deadlocks. In this paper we describe how far contracts can take us in verifying interesting properties of concurrent systems using modular Hoare rules and show how theorem proving methods developed for sequential Eiffel can be extended to the concurrent case. However, some safety and liveness properties depend upon the environment and cannot be proved using the Hoare rules. To deal with such system properties, we outline a SCOOP Virtual Machine (SVM) as a fair transition system. The SVM makes it feasible to use model-checking and theorem proving methods for checking global temporal logic properties of SCOOP programs. The SVM uses the Hoare rules where applicable to reduce the number of steps in a computation. P. J. Brooke, R. F. Paige and Dong Jin Song This work was conducted under an NSERC Discovery grant.     

A unified formal basis for the CASE tools system

XYZ system is a CASE tools system based on a temporal logic language XYZ/E which can represent every essential feature of conventional HLL's (sequential or concurrent), specifications of different levels, production rules, operational semantics of graphic languages in a uniform framework. With this formal language as the common basis, all the CASE tools including various kinds of graphic tools for distributed process, concurrent programs with phased memory and sequential programs, tools for verification, rapid-prototyping, language transformation, and module management can be connected freely to form more sophisticated and integrated systems.     

A Simple, Object-Based View of Multiprogramming

Object-based sequential programming has had a major impact on software engineering. However, object-based concurrent programming remains elusive as an effective programming tool. The class of applications that will be implemented on future high-bandwidth networks of processors will be significantly more ambitious than the current applications (which are mostly involved with transmissions of digital data and images), and object-based concurrent programming has the potential to simplify designs of such applications. Many of the programming concepts developed for databases, object-oriented programming and designs of reactive systems can be unified into a compact model of concurrent programs that can serve as the foundation for designing these future applications. We propose a model of multiprograms and a discipline of programming that addresses the issues of reasoning (e.g., understanding) and efficient implementation. The major point of departure is the disentanglement of sequential and multiprogramming features. We propose a sparse model of multiprograms that distinguishes these two forms of computations and allows their disciplined interactions.     

Apportioning: a technique for efficient reachability analysis ofconcurrent object-oriented programs

The object-oriented paradigm in software engineering provides support for the construction of modular and reusable program components and is attractive for the design of large and complex distributed systems. Reachability analysis is an important and well-known tool for static analysis of critical properties in concurrent programs, such as deadlock freedom. It involves the systematic enumeration of all possible global states of program execution and provides the same level of assurance for properties of the synchronization structure in concurrent programs, such as formal verification. However, direct application of traditional reachability analysis to concurrent object-oriented programs has many problems, such as incomplete analysis for reusable classes (not safe) and increased computational complexity (not efficient). We propose a novel technique called apportioning, for safe and efficient reachability analysis of concurrent object-oriented programs, that is based upon a simple but powerful idea of classification of program analysis points as local (having influence within a class) and global (having possible influence outside a class). We have developed a number of apportioning-based algorithms, having different degrees of safety and efficiency. We present the details of one of these algorithms, formally show its safety for an appropriate class of programs, and present experimental results to demonstrate its efficiency for various examples     

On the applicability of Weyuker Property 9 to object-orientedstructural inheritance complexity metrics

In the metric suite for object oriented design put forward by S.R. Chidamber and C.F. Kemerer (1994), it is observed that E. Weyuker's (1988) Property 9 is not satisfied by any of the structural inheritance complexity metrics. The same is also observed for candidate structural inheritance complexity metrics proposed by A.F. Brito and R. Carapuca (1994). The authors formally show that particular classes of inheritance metrics (that include the above proposals) that are defined on a directed graph abstraction of the inheritance structure and that are contrived on the assumptions and definitions given by Chidamber and Kemerer, can never satisfy Property 9. Furthermore, it is also argued that the formalisation can be generalized to include other classes of structural metrics that are not necessarily inheritance metrics     

Precise slicing of concurrent programs

While there exist efficient algorithms to slice sequential programs precisely, there are only two algorithms for precise slicing of concurrent interprocedural programs with recursive procedures (Krinke in Proc. ESEC/FSE’03, pp. 178–187, 2003; Nanda and Ramesh in ACM Toplas. 28(6):1088–1144, 2006). We present an empirical evaluation of both algorithms for Java. We demonstrate that both algorithms provide the same precision up to the model of concurrency in use and show that the concurrency model has strong impact on slice precision and computation costs. Furthermore, we extend both algorithms to support dynamic thread creation both in loops and recursion—a feature that the original algorithms could not fully handle. The worst case complexity of the algorithms being exponential, we developed several optimizations and compared these with each other and with algorithms that trade precision for speed. Finally, we show that one algorithm may produce incorrect slices and present a remedy.     

一个用于Java程序可达性测试的改进方案

Java程序的并发性使它比串行程序更难测试,而可达性测试是一种有效的并发程序测试方法。首先比较了现有的Java程序可达性测试技术,进而提出了一种融合的改进方案以提高同步序列集的生成效率。然后指出新方案已覆盖了用伯恩斯坦条件裁减同步序列集的功能。最后详述如何通过扫描源程序来自动获取同步事件的时序约束关系,进而减少不可行的同步序列,并介绍了相应的实现算法和数据结构。     

An Experimental Study of Software Metrics for Real-Time Software

The rising costs of software development and maintenance have naturally aroused intere5t in tools and measures to quantify and analyze software complexity. Many software metrics have been studied widely because of the potential usefulness in predicting the complexity and quality of software. Most of the work reported in this area has been related to nonreal-time software. In this paper we report and discuss the results of an experimental investigation of some important metrics and their relationship for a class of 202 Pascal programs used in a real-time distributed processing environment. While some of our observations confirm independent studies, we have noted significant differences. For instance the correlations between McCabe's control complexity measure and Halstead's metrics are low in comparison to a previous study. Studies of the type reported here are important for understanding the relationship between software metrics.