9512.net

甜梦文库

甜梦文库

当前位置：首页 >> >> # 1, 2 Execution of Object-Oriented Software

HKU CSIS Tech Report TR-2003-04

To appear in Proceedings of the 2003 IEEE International Conference on Systems, Man, and Cybernetics (SMC 2003), IEEE Computer Society Press, Los Alamitos, California (2003)

A Scheme for Dynamic Detection of Concurrent Execution of Object-Oriented Software 1, 2

Huo Yan Chen, Yu Xia Sun

Department of Computer Science, Jinan University, Guangzhou 510632, P. R. China

T. H. Tse

Department of Computer Science and Information Systems, The University of Hong Kong, Hong Kong Abstract — Program testing is the most widely adopted approach for assuring the quality and reliability of software systems. Despite the popularity of the object-oriented programs, its testing is much more challenging than that of the conventional programs. We proposed previously a methodology known as TACCLE for testing object-oriented software. It has not, however, addressed the aspects of concurrency and non-determinism. In this paper, we propose a scheme for dynamically detecting and testing concurrency in object-oriented software by executing selected concurrent pairs of operations. The scheme is based on OBJSA nets and addresses concurrency and nondeterminism problems. An experimental case study is reported to show the effectiveness of the scheme in detecting deadlocks, race conditions and other coherence problems. The scheme supplements our previous static approach to detecting deadlock in Java multithreaded programs. Keywords: Object-oriented program testing, dynamic detection and testing, concurrency, OBJSA net Various approaches to testing object-oriented software systems have been proposed [5, 6, 8, 9, 10, 11]. For example, we proposed in [6] a methodology TACCLE to test object-oriented software system at the class and cluster levels. We also presented in [5] an approach for statically detecting object-oriented software system at the method level. These earlier results, however, did not cater for concurrent or nondeterministic situations. Because of the popularity of Java and its strong multi-thread mechanisms, the dynamic testing of concurrency and non-determinism in object-oriented software systems is of increasing importance and should be addressed properly. Carver and Tai [4] proposed to use sequencing constraints for specification-based testing of concurrent programs. Despite the effectiveness of the approach, the sequencing constraints only specified preceding and succeeding events in the concurrent system under test. They did not express other requirements and properties of the system. Zhu and He [12] proposed several adequacy criteria for testing concurrent systems based on high-level Petri nets and also proved subsumption relationships among them. They did not, however, provide techniques for constructing test cases to cover all or part of the criteria. In this paper, we propose a scheme for dynamically detecting and testing concurrency in object-oriented software by executing selected concurrent pairs of operations. Our scheme is based

1. Introduction

Object-oriented paradigm is becoming the main methodology for software systems analysis and design. The testing of object-oriented software, however, is more complex and difficult than that of conventional programs.

1 ?2003 IEEE. This material is presented to ensure timely dissemination of scholarly and technical work. Personal use of this material is permitted. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author’s copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder. Permission to reprint / republish this material for advertising or promotional purposes or for creating new collective works for resale or redistribution to servers or lists, or to reuse any copyrighted component of this work in other works must be obtained from the IEEE. 2 This research is supported in part by the National Natural Science Foundation of China under Grant #60173038, the Guangdong Province Science Foundation under Grant #010421, and the Research Grants Council of Hong Kong.

1

on OBJSA-net/CLOWN specifications [1, 2], which have been successfully used in a large and significant project proposed by the Italian electricity company ENEL. We shall present the background concepts of OBJSA nets in the next section. We shall then discuss our proposed scheme in the subsequent sections.

An extended SA net N is said to be closed if OP = OT = ?, and open otherwise. The nets generated only by classes in CP are called elementary subnets of N. Given an extended SA net N = (P, T, F, W, ∏) and an algebraic specification SPEC = (S, Opt, Eq), an OBJSA component is a SPEC-inscribed net (N, ins, SPEC) with an initial marking (or initial state) M0, where ins = (?, λ, η) is a SPEC-inscription of N such that: (a) ?: P → S is a sort assignment function, which divides places into various sorts (or object classes) while respecting the partition Π. Each element of sort ?(p) is known as a token. It is of the form <ni,j, di,j>, where ni,j ∈ Nt denotes the name of the token and di,j ∈ D denotes its data content. (b) λ: T → ΣS is a ?-respecting arc labeling function, which assigns labels to the arcs surrounding every transaction as follows: For every t ∈ T, let ot = {p1, p2, …, pa} and t o = {q1, q2, …, qb}. For every arc f = (pi, t), if f is open, its label is a variable xi,1 of sort ?(pi); otherwise its label is of the form xi,1 <+> xi,2 <+> … <+> xi,W(f), where each xi,j is a variable of sort ?(pi). Let Xt be a list of variables that label the input arcs of t. For every arc f = (t, qk), if f is open, its label is a term yk,1(Xt); otherwise its label is of the form yk,1(Xt) <+> yk,2(Xt) <+> … <+> yk,W(f)(Xt), where each yk,j(Xt) is a term of sort ?(qk). Furthermore, for each variable xi,j = <ni,j, di,j> in Xt, there exists a unique term yk,r(Xt) = <nk,r*, dk,r*> of sort ?(qk) such that nk,r* = ni,j and dk,r* = σt(…, di,j, …) for some function σt that specifies the change of the data content due to the transition t. (c) η: T → Bool is an inscription function that assigns to every transaction t a pre-condition η(t, Xt) for firing it. M0 associates with each closed place p a multi-set of tokens of sort ?(p), under the condition that if the name of a token appears in the marking of a place, it must not appear in the marking of any other place of the same elementary component. An open place op ∈ OP is associated with all the possible terms of the sort ?(op).

2. Background Concepts

To lay the foundations of the paper, we present in this section the basic concepts of OBJSA nets originally proposed in [1, 2]. We shall adhere as much as possible to the notation of [2] for the ease of understanding and comparison. A net is a triple N = (P, T, F), where P, T, and F are finite non-empty sets such that P ∩ F = ? and F ? (P × T) ∪ (T × P). The elements of P, T, and F are known as places, transitions, and arcs, respectively. In general, places are used to model conditions or system resources, and transitions are used to model operations or actions. Let V = P ∪ T be the set of vertices of N. For any v ∈ V, ov = {y | y ∈ V ∧ (y, v) ∈ F} is called the pre-set of v, and vo = {y | y ∈ V ∧ (v, y) ∈ F} is called the post-set of v. An extended SA net is a tuple N = (P, T, F, W, ∏), where (P, T, F) is a net. Places in P are partitioned into two disjoint classes OP and CP. The elements of OP are called open places and those of CP are called closed places. Transitions in T are partitioned into two disjoint classes OT and CT. The elements of OT are called open transitions and those of CP are called closed transitions. An arc f ∈ OF ? (OP × OT) ∪ (OT × OP) is said to be an open arc. An arc f ∈ CF ? (CP × T) ∪ (T × CP) is said to be closed. W: F → Nat is the arc weight function, where Nat denotes the set of natural numbers. In particular, W(f) = 1 for every open arc f. ∏ is a partition of P into disjoint classes ∏1, ∏2, …, ∏m such that every ∏i contains either open places only or closed places only, and for every t ∈ T, Σp∈(∏i∩ot)W(p, t) = Σp∈(∏i∩ot)W(t, p).

2

An OBJSA net is constructed in a bottom-up manner. An OBJSA component is said to be elementary if the underlying net N contains only one elementary subnet. An OBJSA component is said to be open if the underlying net N is open. They are constructed by composing elementary or other open

Producers generate <np2, dp2> p2 <np1, dp1*> send pr1 <na1, da1> <np2, dp2*> p1 <np1, dp1>

components together. An OBJSA net is a closed OBJSA component, formed by composing elementary or open OBJSA components, such that the underlying net N is closed. Details of composition rules can be found in [2].

Consumers consume <nc2, dc2> c1 <nc1, dc1*> receive <na4, da4*> pr3 <nc2, dc2*> c2 <nc1, dc1>

<na1, da1*>

a1 <na4, da4> <na3, da3> <na2, da2*> a3 <na3, da3*> pr2 Agents

a2

<na2, da2> exchange

np1, np2, nc1, nc2, na1, na2, na3, na4: ObjectName in the form [type: Type, id: Nat], where Type denotes the set of object sorts, Nat denotes the set of natural numbers, type ∈ {p, c}, p denotes producer, c denotes consumer, and id denotes the object identifier. da1, da2, da3, da4, da1*, da2*, da3*, da4*: FullMessage in the form [msg: Message, dest: Nat], where dest denotes a destination object. da1* = dp1. da2* = nullmsg. da3* = da2. da4* = nullmsg. dp1, dp2, dp1*, dp2*, nullmsg: FullMessage. dp1* = nullmsg. dp2* = produceMessage(np2). dc1, dc2, dc1*, dc2*, null: Message. dc1* = msg(da4). dc2* = null. pr1, pr2, pr3: Bool. pr1 = (type(na1) = = p) ∧ (id(na1) = = id(np1)). pr2 = (type(na2) = = p) ∧ (type(na3) = = c) ∧ (dest(da2) = = id(na3)). pr3 = (type(na4) = = c) ∧ (id(na4) = = id(nc1)).

Figure 1. OBJSA Net Specifying the System in Example 1

3

Given an OBJSA component with a transition t ∈ T such that ot = {p1, p2, …, pa} and t o = {q1, q2, …, qb}, a firing mode for t is an assignment function βt: Xt → T?(pi) that associates a ground term of sort ?(pi) to every variable xi,j in the list Xt. Given a firing mode βt, for each place p∈P, IN(p, t) is defined as follows: (a) IN(p, t) = {βt(xi,j) | j = 1, 2, ..., W(p, t)} if p = pi ∈ ot ∩ CP; (b) IN(p, t) = {β t(xi,1)} if p = pi ∈ ot ∩ OP; (c) IN(p, t) = ? otherwise. Given a marking M, a transition t ∈ T and a firing mode βt, we say that t is βt-enabled at M if, for each place pi ∈ ot, IN(pi, t) ? M(pi) and η(t, βt) = true. An enabled transition at the initial marking M0 of an OBJSA net is called a source transition. Starting with M0, the number of times that a source transition can be consecutively fired is known as the index of the source transition. A source transition with the largest index is called the greatest source transition. In order to help readers understand OBJSA net concepts, we give here an example adapted from [2]. After we have discussed our scheme in Sections 3 and 4, we shall revisit this example in an experimental case study in Section 5. Example 1. Suppose a system comprises 5 producers and 4 consumers asynchronously exchanging messages through a network of 5 + 4 agents. The constituents of the system can be specified by OBJSA open components Producers, Consumers, and Agents, respectively. The OBJSA net specifying the system is shown in Figure 1. Its initial marking M0 is as follows: M0(p2) = {<[p, 1], nullmsg>, <[p, 2], nullmsg>, <[p, 3], nullmsg>, <[p, 4], nullmsg>, <[p, 5], nullmsg>}; M0(c2) = {<[c, 1], null>, <[c, 2], null>, <[c, 3], null>, <[c, 4], null>}; M0(a1) = {<[p, 1], nullmsg>, <[p, 2], nullmsg>, <[p, 3], nullmsg>, <[p, 4], nullmsg>, <[p, 5], nullmsg>, <[c, 1], null>, <[c, 2], null>, <[c, 3], null>, <[c, 4], null>}; M0(p) = ? for p ∈ P ? {p2, c2, a1}.

3. Our Scheme

This section describes our scheme for dynamically detecting and testing concurrency in object-oriented software by simultaneously executing selected concurrent pairs. Given an OBJSA net Osn, let Mi be a reachable marking. If two transitions ti1 and ti2 (or their corresponding operations) can be fired simultaneously at Mi, we say that ti1 and ti2 are a concurrent pair at Mi. In formal terms, ti1 and ti2 are a concurrent pair at Mi if and only if (ti1 and ti2 are enabled respectively) and ??p (p∈ oti1 ∩ oti2 ∧ ?βt (IN(p, ti2) ? Mi(p) ? IN(p, ti1))). For simplicity, let I1, I2, and M denote IN(p, ti1), IN(p, ti2), and Mi(p), respectively. It can easily be proved that if I1 ? M and I2 ? M, then (a) I2 ? M ? I1 implies I1 ∩ I2 ≠ ? and (b) I2 ? M ? I1 if and only if I1 ? M ? I2. Hence, the expression IN(p, ti2) ? Mi(p) ? IN(p, ti1) above can be replaced by IN(p, ti1) ? Mi(p) ? IN(p, ti2). In other words, ti1 and ti2 will be a concurrent pair at Mi if and only if (ti1 and ti2 are enabled respectively) and ??p (p ∈ oti1 ∩ oti2 ∧ ?βt (IN(p, ti1) ? Mi(p) ? IN(p, ti2))). Let τ be a sequence of individual or concurrent τ transitions. The notation Mi ? ?→ Mj means that, starting with the marking Mi, we can consecutively fire the transitions in τ to obtain the marking Mj.

i1 i 2 When τ is null, Mi = Mj. The notation Mi ?? ?→ Mj means that simultaneously firing ti1 and ti2 at Mi will i1 i 2 obtain the marking Mj. In fact, Mi ?? ?→ Mj can be taken as a test case.

t ||t

t ||t

τi ?→ Mi, where M0 is the initial marking If M0 ? of Osn, we say that Mi can be reached by τi. Thus, the

i1 i 2 test case Mi ?? ?→ Mj can be written as τi ? ti1||ti2, which means that we can reach Mj if we start from M0, consecutively fire the individual or concurrent transitions in τi, and then simultaneously fire the concurrent pair ti1 and ti2.

t ||t

Let t0 be the greatest source transition of a given OBJSA net Osn. Our scheme for selecting concurrent

i1 i 2 test cases of the form Mi ?? ?→ Mi+1, or τi ? ti1||ti2, contains the following steps:

t ||t

4

(1) set Mc := M0, Tc := {t0}, τc := null, and i := 1; (2) if there is a sequence (t0, t1, …, tk) of transitions in Tc (where k < |Tc|) such that, starting with Mc, we can reach Mi after firing t0 ? t1 ? … ? tk, that is, Mc ?? ? ? ?→ Mi, and if we can find ti1 (? Tc) and ti2 (∈ Tc) that can be fired simultaneously at Mi, then {

i1 i 2 ?→ Mi+1, Tc := Tc ∪ {ti1}, τi := τc ? Mi ?? t0 ? t1 ? … ? tk, and τc := τi ? ti1||ti2; return a test case τi ? ti1||ti2; }; else exit from the scheme;

each test case τi ? ti1||ti2 obtained in the proposed scheme. Details of replay techniques can be found in [3]. Our approach can expose various errors due to concurrency, such as deadlocks, race conditions, and other coherence problems. The scheme can be applied not only to Java programs, but also to programs of other languages that support concurrency.

t0 ? t1 ? K ? tk

t ||t

5. Experimental Case Study

Applying the above scheme to Example 1, we obtained the following test cases: τ1 ? t11||t12 = t0 ? t1||t0; τ2 ? t21||t22 = t0 ? t1||t0 ? t2||t3; τ3 ? t31||t32 = t0 ? t1||t0 ? t2||t3 ? t3||t2; τ4 ? t41||t42 = t0 ? t1||t0 ? t2||t3 ? t3||t2 ? t4||t3; where t0 = generate, t1 = send, t2 = exchange, t3 = receive, and t4 = consume. We implemented a Java system consisting of 5 producers and 4 consumers as specified in Example 1, and then injected deadlocks, race conditions and other coherence problems into the program. All the injected faults were revealed by our approach.

(3) i := i +1; if we can find ti1 (? Tc) and ti2 (∈ Tc ? {t0}) that can be fired simultaneously at Mi, then {

i1 i 2 Mi ?? ?→ Mi+1, Tc := Tc ∪ {ti1}, τi := τc, and τc := τc ? ti1||ti2; return a test case τi ? ti1||ti2; go to (3); }; else set Mc := Mi and go to (2);

t ||t

4. Discussions

We presented in [7] an approach to detecting deadlocks in Java multithreaded programs. It constructs Calling Hierarchy Diagrams and LockCalling-Suspend Diagrams from the programs under test, and then analyzes special properties to determine whether is there are potential deadlocks in the programs. The approach is static and white-box based. It cannot, for instance, find deadlocks due to dynamic binding. As a supplement to the approach described in [7], the scheme introduced in the last section of this paper is for detecting and testing concurrency in objectoriented software by executing selected concurrent pairs of operations. It is dynamic and black-box based. It can detect deadlocks due to dynamic binding. Because of non-determinism in concurrent programs, we must use replay techniques to execute

6. Conclusion

We have presented a black-box and dynamic scheme for detecting and testing concurrency in object-oriented software by executing selected concurrent pairs of operations based on OBJSA-net specifications. An experimental case study has also been reported. More case studies and experiments will be conducted as future research.

Acknowledgement

We would like to express our thanks to Shuang Quan Li for the implementation and experiments in the case study.

5

References

[1] Battiston E., A. Chizzoni, and F. D. Cindio. CLOWN as a testbed for concurrent objectoriented concepts. In Concurrent ObjectOriented Programming and Petri Nets: Advances in Petri Nets, pages 131–163. Lecture Notes on Computer Science, Springer, Berlin, 2001. [2] Battiston E., F. de Cindio, and G. Mauri. Modular algebraic nets to specify concurrent systems. IEEE Transactions on Software Engineering, 22 (10): 689–705, 1996. [3] Carver R. H. and K.-C. Tai. Replay and testing for concurrent programs. IEEE Software, 8 (3): 66–74, 1991. [4] Carver R. H. and K.-C. Tai. Use of sequencing constraints for specification-based testing of concurrent programs. IEEE Transactions on Software Engineering, 24 (6): 471–490, 1998. [5] Chen H. Y. The design and implementation of a prototype for data flow analysis at the methodlevel of object-oriented testing. In Proceedings of the 2002 IEEE International Conference on Systems, Man, and Cybernetics (SMC 2002), pages 140–145. IEEE Computer Society Press, Los Alamitos, California, 2002. [6] Chen H. Y., T. H. Tse, and T. Y. Chen. TACCLE: a methodology for object-oriented software testing at the class and cluster levels. ACM Transactions on Software Engineering and Methodology, 10 (1): 56–109, 2001.

[7] Chen H. Y. Race condition and concurrency safety of multithreaded object-oriented programming in Java. In Proceedings of the 2002 IEEE International Conference on Systems, Man, and Cybernetics (SMC 2002), pages 134–139. IEEE Computer Society Press, Los Alamitos, California, 2002. [8] Doong R.-K. and P. G. Frankl. The ASTOOT approach to testing object-oriented programs. ACM Transactions on Software Engineering and Methodology, 3 (2): 101–130, 1994. [9] Kung D. C., J. Z. Gao, P. Hsia, Y. Toyoshima, and C. Chen. A test strategy for object-oriented programs. In Proceedings of the 19th Annual International Computer Software and Applications Conference (COMPSAC ’95), pages 239–244. IEEE Computer Society Press, Los Alamitos, California, 1995. [10] Smith M. D. and D. J. Robson. A framework for testing object-oriented programs. Journal of Object-Oriented Programming, 5 (3): 45–53, 1992. [11] Turner C. D. and D. J. Robson. A state-based approach to the testing of class-based programs. Software: Concepts and Tools, 16 (3): 106–112, 1995. [12] Zhu H. and X. He. A theory of testing high-level Petri nets. In Proceedings of the International Conference on Software: Theory and Practice, 16th IFIP World Computer Congress, pages 443–450. Beijing, China, 2000.

6

赞助商链接

- An Improved Suite of Object Oriented Software Measures
- A COMPARISON OF SOFTWARE REUSE SUPPORT IN OBJECT-ORIENTED METHODOLOGIES
- The ADORA Approach to Object-Oriented Modeling of Software
- Co-evolution of Object-Oriented Software Design and Implementation
- Design, Distribution and Management of Object-Oriented Software

更多相关文章：
**
BurrisJavaObj***Oriented1*课件_图文

1) Non-self-modifying code*2*) Separate data ...*execution* to next) "*Object* *Oriented* Design," by..."Understanding *Software* Through Analysis *of* Empirical...**
《计算机英语(第***2*版)》参考答案

其他未改动课文答案参 见《计算机英语(第*1* 版) ...(entity) *2*. One *of* the disadvantages *of* model-...With reusable *object-oriented* *software,* your design...**
Answer4
**

.*Software* Engineering Multiple Choice Questions *1*....notational system for representing *object-oriented* ...Tree ANSWER: B *2*. Which *of* the following is ...**
AN ***OBJECT* *ORIENTED* C++ PARALLEL COMPILER SYSTEM

*1*/*2* 相关文档推荐 An Implementation *of* a P......comprehensibility and reusability *of* the *software* ...*execution* *of* parallel entities *of* a state *object* ...**
教学大纲-软件工程
**

软件工程*二*、课程类型必修课 三、课程地位(作用)...Schach*,* *Object-Oriented* *Software* Engineering*,1*th ...*of* Maintenance Programmers Challengers *of* the ...**
面向对象软件测试综述
**

*of* *object-oriented* *software,*and is the key to *software* quality and ...*2*.*1* 软件测试的方法 *2*.*2*.*1* 黑盒测试 黑盒测试又称为功能测试,是*一*种面向...**
面向对象中外文翻译
**

1 面向对象(文献翻译)*2* Question 1: what is ...dynamics *of* *object-oriented* *software* development ...action *of* parallel *execution* and message specification...**
软件工程(双语)考试试卷
**

the primary benefits*of* *object-oriented* ...improved *execution* performance D)simplified interfaces...(Each *2*, total 10 Points) (( )1.“*Software*...**
c++编程-外文文献
**

1 毕业设计(论文)外文资料翻译 1.*Software* Design...branching to control the flow *of* *execution*. THE...The *object- oriented* paradigm retains much *of* the...**
The ***Object-Oriented* Programming on My Sight

Java is a kind*of* *object-oriented* language. But...Reference: *1*. Stroustrup, B., 1988. What is ...IEEE *software,* 5(3), pp.10-20. *2*. Fouché ...
更多相关标签：

1) Non-self-modifying code

其他未改动课文答案参 见《计算机英语(第

.

软件工程

1 面向对象(文献翻译)

the primary benefits

1 毕业设计(论文)外文资料翻译 1.

Java is a kind