GTM-MQNC2Z4
Skip to main content
  1. Home >
  2. About Fujitsu >
  3. Resource Center >
  4. News >
  5. Press releases >
  6. 2010>
  7. Fujitsu Accelerates Exhaustive Verification of Java Software Through Parallel Processing

Fujitsu Accelerates Exhaustive Verification of Java Software Through Parallel Processing

Step toward practical use of verification technology that enables program quality enhancement

Fujitsu Laboratories of America Inc.,Fujitsu Laboratories Ltd.

Sunnyvale, U.S. and Kawasaki, Japan, December 17, 2010

Fujitsu Laboratories of America, Inc. and Fujitsu Laboratories Ltd. today announced the development of technology enabling high-speed exhaustive verification of Java software using parallel processing. In order to ensure the quality of ICT systems, it is critical that software programs be sufficiently tested. By employing this new technology that leverages the power of cloud computing, on previous technologies enabling exhaustive verification of programs developed by Fujitsu Laboratories, time required for verification can be dramatically shortened, leading to expectations that the technology will result in enhancement of program quality.

About Program Verification

Ensuring the quality of ICT systems that are at the heart of businesses today requires thorough testing to verify whether the programs that provide the system's functionality work as expected. Testing the underlying software of a shopping website, for example, involves generating numerous test cases (test case generation) that represent different permutations of user actions and circumstances, such as whether or not a product ID or the correct quantity was entered, and generating data for each permutation (test data generation) to be fed, one at a time, into the software program. Using these data, programmers must check that the program actually operates properly (verification through testing) (Figure 1).

Figure 1: Test case and test data generation

Larger View (84 KB)

Background

Java PathFinder, a verification tool developed by the National Aeronautics and Space Administration (NASA)(1) in the United States, provides functions for automatically executing tests on Java programs using a technique called symbolic execution(2), without the need to manually enter any test cases or test data. Fujitsu Laboratories has worked to expand these functions, making it possible to process character string data, which accounts for much of the data typically processed by business applications, thus enabling verification of business applications that entail such character string data (Figure 2).

Figure 2: Overview of symbolic execution

Larger View (96 KB)

Technological Challenges

With existing technologies, the processing time involved in verifying programs containing a few tens of thousands of lines of code, even with a restricted input data set, can take several hours. As a result, it has become an important challenge to develop technology that shortens this verification time.

Newly-developed Technology

Fujitsu Laboratories has developed technology that performs verification of Java software in parallel. This makes it possible to accelerate the verification process by leveraging the computational power of cloud computing. In an experiment using ten processing nodes, the new software achieved approximately ten times the performance of existing technology.

Key features of the new technology are follows:

1. Parallelization technology that divides the symbolic execution processing and allocates it across multiple processing nodes

With symbolic execution, a search process is performed on a program's tree structure that traces the conditional branches within the program. Fujitsu's new technology divides this tree structure and allocates parts of it to multiple processing nodes, accelerating the testing by processing these branches in parallel (Figure 3-1).

2. Dynamic load balancing reallocates the processing of overloaded nodes to idle nodes

Depending on the program contents, an imbalance may occur in the traversal loads that are allocated to each node, making it impossible to reduce processing time, even via parallelized execution. The new technology monitors the traversal of each node, and if its processing is not finished within a specified period of time, the monitoring function repartitions the heavy computation at that node and reallocates the partitions to other nodes that are finished and lying idle. This balances out the processing load of each node, thereby preserving the speed-up obtained through parallelized processing (Figure 3-2).

Figure 3: Parallelization and load-leveling of symbolic execution

Larger View (72 KB)

Results

Increasing the number of processing nodes through methods like cloud computing makes it possible to quickly verify large-scale programs. This is expected to greatly contribute to improving the quality of software programs.

Future Developments

Fujitsu Laboratories is continuing to enhance this technology through internal testing, and aims to commercialize it during fiscal 2011 (April 2011 - March 2012). The company is also considering offering the technology as a cloud-based service.


  • [1] The National Aeronautics and Space Administration (NASA)

    A U.S. government agency responsible for aerospace research.

  • [2] Symbolic execution

    A program execution method in which all test data are represented in symbolic form. During execution, the program performs case analysis of the program within the scope of the symbols, based on its branching conditions, thereby enabling each path to be executed.

About Fujitsu Laboratories of America, Inc.

Fujitsu Laboratories of America, Inc. is a wholly owned subsidiary of Fujitsu Laboratories Ltd. (Japan), focusing on research on advanced VLSI CAD, Internet, and interconnect technologies. Conducting research in an open environment, it contributes to the global research community and the working IT industry. It is headquartered in Sunnyvale, CA.
For more information, please see: www.fla.fujitsu.com

About Fujitsu Laboratories

Founded in 1968 as a wholly owned subsidiary of Fujitsu Limited, Fujitsu Laboratories Limited is one of the premier research centers in the world. With a global network of laboratories in Japan, China, the United States and Europe, the organization conducts a wide range of basic and applied research in the areas of Next-generation Services, Computer Servers, Networks, Electronic Devices and Advanced Materials. For more information, please see: http://jp.fujitsu.com/labs/en.

Press Contacts

Public and Investor Relations Division
Inquiries

Company:Fujitsu Limited

Technical Contacts

Software Innovation Lab.
Software and Solutions Lab.

Phone: Phone: +81(44)754-2675
E-mail: E-mail: java-verification@ml.labs.fujitsu.com
Company:Fujitsu Laboratories Ltd.


Company and product names mentioned herein are trademarks or registered trademarks of their respective owners. Information provided in this press release is accurate at time of publication and is subject to change without advance notice.

Date: 17 December, 2010
City: Sunnyvale, U.S. and Kawasaki, Japan
Company: Fujitsu Laboratories of America, Inc., Fujitsu Laboratories Ltd., , , , , , , , ,