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



更多相关文章:
《计算机英语(第2版)》参考答案
其他未改动课文答案参 见《计算机英语(第 1 版) ...(entity) 2. One of the disadvantages of model-...With reusable object-oriented software, your design...
BurrisJavaObjOriented1课件_图文
1) Non-self-modifying code 2) Separate data ...execution to next) "Object Oriented Design," by..."Understanding Software Through Analysis of Empirical...
() is a property of object-oriented software by whi...
() is a property of object-oriented software by...理科数学 北京海淀区2016年高三第次模拟考试 理科...北京师范大学第附属中学©2016 Baidu 使用百度前...
软件人员推荐书目(国外经典)
2 版)"(Object-Oriented Software Construction,Second Edition ) 【32】 "...of Reusable Object-Oriented software) 【38】 "面向模式的软件体系结构 卷 1...
计算机专业英语作业2
计算机专业英语作业 2 第 4-6 章作业一.Vocabulary...Object-oriented Design (OOD) 9. software testing...which is defined as the execution of a program ...
软件工程专业培养方案-2012
软件工程专业培养方案、专业名称与代码:软件工程(...2. To master the basic knowledge and theory of...Object-Oriented Software Engineering & UML, Java ...
软件人员推荐书目(都是国外经典书籍!!!)
大师篇 、 科学哲学和管理哲学 【1】 "程序开发心理学"(The Psychology of...第 2 版)"(Object-Oriented Software Construction,Second Edition ) 【32】 "...
Computer -English
与执行 program storage and execution 五单元 1. ...基于组件的软件工程 component-based software ...object-oriented database 面向对象数据库 7. ...
...​ ​曾​​墙​ ​2​0​0​8...
2​0​0​8​11​8​5​0​1...execution environment, even in the presence of ...The system provides a consistent, object-oriented ...
好的软件人员必看的60本书
Elements of Reusable Object-Oriented software) 75 【38】 “面向模式的软件体系结构 卷 1:模式系统”( Pattern-Oriented Software Architecture, Volume 1: A Sy...
更多相关标签:

All rights reserved Powered by 甜梦文库 9512.net

copyright ©right 2010-2021。
甜梦文库内容来自网络,如有侵犯请联系客服。zhit325@126.com|网站地图