IEICE TRANS. INF. & SYST., VOL.Exx–??, NO.xx XXXX 200x1LETTER

Towards Logging Optimization for Dynamic Object Process GraphConstruction
Takashi ISHIO†a) , Member, Hiroki WAKISAKA†b) , Yuki MANABE††c) , Nonmembers,
and Katsuro INOUE†d) , Fellow

SUMMARY Logging the execution process of a program is a popular
activity for practical program understanding. However, understanding thebehavior of a program from a complete execution trace is diﬃcult becausea system may generate a substantial number of runtime events. To focus ona small subset of runtime events, a dynamic object process graph (DOPG)
has been proposed. Although a DOPG can potentially facilitate program
understanding, the logging process has not been adapted for DOPGs. If
a developer is interested in the behavior of a particular object, only theruntime events related to the object are necessary to construct a DOPG. The
vast majority of runtime events in a complete execution trace are irrelevantto the interesting object. This paper analyzes actual DOPGs and reports thata logging tool can be optimized to record only the runtime events related toa particular object specified by a developer.
key words: dynamic analysis, logging, program understanding, dynamicobject process graph

1. Introduction
Logging the execution process of a program is a popular activity for practical program understanding [1]. However, it
is challenging to record and analyze a substantial numberof runtime events. For example, developers are investigating a web server problem. Developers have to identify therequests from clients that caused the failures from an execution trace, even if the vast majority of events in the trace arerelated to successful requests.
To focus on a small subset of runtime events which arerelated to the behavior of a single object, a dynamic object
process graph (DOPG) can be used [2], [3]. A DOPG is apartial control-flow graph for a single object, which connects only executed instructions such as branches, method
calls, and field access related to the object. Figure 1 showsa source code fragment including three control-flow paths.
While its control-flow graph includes 11 nodes, a DOPG foran object created by the shaded path includes 6 nodes asshown on the right side of Figure 1. The other nodes areexcluded from the DOPG because they are irrelevant to theobject.
Manuscript received January 1, 2013.
Manuscript revised January 1, 2013.
†Graduate School of Information Science and Technology, Osaka University, 1-5 Yamadaoka, Suita, Osaka, 565-0871, Japan††
Graduate School of Science and Technology, Kumamoto University, 2-39-1 Kurokami, Chuo-ku, Kumamoto 860-8555, Japana) E-mail: ishio@ist.osaka-u.ac.jpb) E-mail: h-wakisk@ist.osaka-u.ac.jpc) E-mail: y-manabe@cs.kumamoto-u.ac.jpd) E-mail: inoue@ist.osaka-u.ac.jp
DOI: 10.1587/transinf.E0.D.1

1: X x = new X();STARTSTART

2: if (c1) {3:x.f1();

4:x.f2();

1: X x = new X();

1: X x = new X();
2: if (c1) {5: } else {
6:x.f3();

7:x.f4();

8:if (c2) {9:x.f5();

10:} else {11:x.f6();

12: }3: x.f1();

4: x.f2();

6: x.f3();

2: if (c1) {7: x.f4();

3: x.f1();

8: if (c2) {4: x.f2();
9: x.f5();

11: x.f6();END
END

Fig. 1 A sample source code fragment, its control-flow graph and aDOPG for an object created from the shaded control-flow path.

A developer is often interested in the behavior of a particular object in an execution trace. Although a simple logging tool for DOPG may record all the runtime events andthen permit a developer to choose a preferred DOPG, it requires a lot of time and space to record a numerous runtime events and most events are unlikely to be relevant tothe interesting behavior. Therefore, this paper discusses anoptimization approach for DOPG construction that involves
reducing the number of runtime events to be recorded; itrequires a developer to specify the method calls for the object of interest. For example, if a developer is interested inonly the shaded path in Figure 1, the developer can specify
the interesting object that receives a method call at line 3.
A logging tool can discard runtime events for objects thatreach line 6 and ignore events on paths between line 6 andthe end node.
This paper investigates whether actual DOPGs in programs can be specified by method calls and whether a logging tool can be optimized for a DOPG. Because there is noempirical data of DOPGs in literature, the paper analyzes
actual DOPGs from a benchmark suite and discusses possible optimizations.
2. Analysis
A basic idea for optimization is to identify the objects of interest to a developer. This paper evaluates whether a DOPG
can be specified by method calls because a developer will
not know the precise shape of a DOPG of interest before

c 200x The Institute of Electronics, Information and Communication EngineersCopyright ⃝IEICE TRANS. INF. & SYST., VOL.Exx–??, NO.xx XXXX 200x

1: X x = new X();

3: x.f1();

4: x.f2();

A2

1: X x = new X();

6: x.f3();

7: x.f4();

9: x.f5();

A3

1: X x = new X();

6: x.f3();

7: x.f4();

11: x.f6();

DFA accepting method calls on each control-flow path

R(C) =Predict(C)T race(C) + Predict(C)where T race(C) is the total number of edges in the pathslk (solid edges), Predict(C) is the total number of remaining edges (dashed edges). If R(C) is high; a logging tool
can ignore more runtime events for irrelevant objects on an1= 0.09. This indiaverage. In case of Figure 2, R(X) = 10+1
cates that if three control-flow paths are equally selected, alogging tool has to record most of the events for the class.
To compute the R(C) metric in general programs, actual DOPGs are extracted from five applications in the DaCapo benchmarks: avrora, batik, lusearch, pmd, andxalan. The applications include 1015 classes in total. The
analysis excluded 212 classes, which included at least oneobject that satisfied one of the following conditions.
• The object has been concurrently accessed by two ormore threads. This is because a DOPG has not been
defined for a multi-threaded program.
• The object has used recursive calls, because realizable
paths of recursive calls cannot be represented by DFA.
• The DFA of the object has more than 50 states. Thiscondition excludes objects globally used in an application since such a class is likely to be a utility class [4].
In Figure 3, R(C) is plotted for each class in a descending order. 535 classes (66% of the analyzed classes) haveR(C) = 1. Each of these classes is represented by a single
DOPG, i.e., each class is used by a particular sequence ofmethod call sites. To construct a DOPG for these classes,

0.0

execution. If a smaller number of method calls are enoughto identify an object for a DOPG, a logging tool can ignore
additional runtime events that are irrelevant to the DOPG.
A metric for interesting object identification is computed for class C as follows. First, DOPGs are extracted
from all instances of class C. Each DOPG is translated into
a deterministic finite automaton (DFA), which includes only
method call events. Figure 2 shows three DFAs corresponding to three DOPGs of control-flow paths in Figure 1. Next,
the shortest unique path lk is computed for each DFA Ak .
A sequence of method calls is unique to Ak if only Ak has
the path from the initial state (the other DFAs reject lk ). In
Figure 2, the shortest unique paths are indicated by solidedges (10 of 11 edges). To identify an object as relevant
to a DOPG, the object must traverse one of the paths. Forexample, an object was identified as relevant to A1 when it
received the method calls at line 1 and line 3. Finally, themetric R(C) for class C is calculated using the following formula:

0.2

0.4

Fig. 2

R

0.6

A10.8

1.0

20200

400600800ClassesFig. 3R(C) value of 803 classes in descending order.

a logging tool requires only the first single instance created in an execution. A pointer/alias analysis, which identifies source code locations where an object may be used,is also eﬀective for minimizing logging. Many classes areincluded in this category because a single object is created
for a particular feature (or business logic). For example,DisplayManager class in batik manages display properties of the system. ClockDomain class in avrora manages
a dataset for the whole system.
183 classes (24%) have 0 < R(C) < 1. Each of theseclasses has more than two DFAs. The average Predict(C)are 4 method call sites. A logging tool can ignore sectionsof runtime events for these classes as described in Section 1.
In this group, instances are set up in diﬀerent ways after theirinstantiation. For example, StyleSheet and PathParser
classes in batik are included in this group.
The other 85 classes (10%) have R(C) = 0 . Theirinstances have received the same sequence method calls
except for the final method call. Therefore, optimization using method calls are not eﬀective for these classes.
GenericText class in batik is an example of this category.
3. Conclusion
This paper analyzed actual DOPGs in terms of the R(C) metric. The result shows optimized logging could be implemented for 90% of the classes. Although the DOPGs usedin this paper depend on the DaCapo benchmark, optimized
logging for DOPG construction is a promising approach.
Before a new optimized logging tool can be built, twoissues need to be addressed. First, the result might misssome DOPGs, because the benchmark does not cover all
possible execution paths in the programs. More test cases
for improving the path coverage are required to evaluate theeﬀectiveness of the optimization approach more precisely.
Secondly, the new logging tool should incorporate a pointeranalysis (or an alias analysis) to identify method call sites
relevant to interesting objects, because an object can be manipulated by various methods. Furthermore, the eﬀect ofthe precision of the pointer analysis on the performance of alogging tool should be evaluated.

LETTER3

Acknowledgement
This work was supported by JSPS KAKENHI Grant Number 23680001.
References[1] A. Zeller, Why Programs Fail - A Guide to Systematic Debugging,
the Second Edition, Morgan Kaufmann, 2011.
[2] J. Quante and R. Koschke, “Dynamic object process graphs,” Journalof Systems and Software, vol.81, pp.481–501, 2008.
[3] J. Quante, “Do dynamic object process graphs support program understanding?,” Proc. of ICPC, pp.73–82, 2008.
[4] A. Hamou-Lhadj and T. Lethbridge, “Summarizing the content oflarge traces to facilitate the understanding of the behaviour of a software system,” Proc. of ICPC, pp.181–190, 2006.