Important Considerations for Test Automation

Important Considerations for Test Automation

Often when a test automation tool is introduced to a project, the expectations for the return on investment are very high. Project members anticipate that the tool will immediately narrow down the testing scope, meaning reducing cost and schedule. However, I have seen several test automation projects fail - miserably.

The following very simple factors largely influence the effectiveness of automated testing, and if not taken into account, the results is usually a lot of lost effort, and very expensive ‘shelfware’.

1. Scope - It is not practical to try to automate everything, nor is there the time available generally. Pick very carefully the functions/areas of the application that are to be automated.

2. Preparation Timeframe - The preparation time for automated test scripts has to be taken into account. In general, the preparation time for automated scripts can be up to 2/3 times longer than for manual testing. In reality, chances are that initially the tool will actually increase the testing scope. It is therefore very important to manage expectations. An automated testing tool does not replace manual testing, nor does it replace the test engineer. Initially, the test effort will increase, but when automation is done correctly it will decrease on subsequent releases.

3. Return on Investment - Because the preparation time for test automation is so long, I have heard it stated that the benefit of the test automation only begins to occur after approximately the third time the tests have been run.

4. When is the benefit to be gained? Choose your objectives wisely, and seriously think about when & where the benefit is to be gained. If your application is significantly changing regularly, forget about test automation - you will spend so much time updating your scripts that you will not reap many benefits. [However, if only disparate sections of the application are changing, or the changes are minor - or if there is a specific section that is not changing, you may still be able to successfully utilise automated tests]. Bear in mind that you may only ever be able to do a complete automated test run when your application is almost ready for release – i.e. nearly fully tested!! If your application is very buggy, then the likelihood is that you will not be able to run a complete suite of automated tests – due to the failing functions encountered.

5. The Degree of Change – The best use of test automation is for regression testing, whereby you use automated tests to ensure that pre-existing functions (e.g. functions from version 1.0 - i.e. not new functions in this release) are unaffected by any changes introduced in version 1.1. And, since proper test automation planning requires that the test scripts are designed so that they are not totally invalidated by a simple gui change (such as renaming or moving a particular control), you need to take into account the time and effort required to update the scripts. For example, if your application is significantly changing, the scripts from version 1.0. may need to be completely re-written for version 1.1., and the effort involved may be at most prohibitive, at least not taken into account! However, if only disparate sections of the application are changing, or the changes are minor, you should be able to successfully utilise automated tests to regress these areas.

6. Test Integrity - how do you know (measure) whether a test passed or failed ? Just because the tool returns a ‘pass’ does not necessarily mean that the test itself passed. For example, just because no error message appears does not mean that the next step in the script successfully completed. This needs to be taken into account when specifying test script fail/pass criteria.

7. Test Independence - Test independence must be built in so that a failure in the first test case won't cause a domino effect and either prevent, or cause to fail, the rest of the test scripts in that test suite. However, in practice this is very difficult to achieve.

8. Debugging or "testing" of the actual test scripts themselves - time must be allowed for this, and to prove the integrity of the tests themselves.

9. Record & Playback - DO NOT RELY on record & playback as the SOLE means to generates a script. The idea is great. You execute the test manually while the test tool sits in the background and remembers what you do. It then generates a script that you can run to re-execute the test. It's a great idea - that rarely works (and proves very little).

10. Maintenance of Scripts - Finally, there is a high maintenance overhead for automated test scripts - they have to be continuously kept up to date, otherwise you will end up abandoning hundreds of hours work because there has been too many changes to an application to make modifying the test script worthwhile. As a result, it is important that the documentation of the test scripts is kept up to date also.

Author - Bazman, http://members.tripod.com/~bazman/auto.html?button2=Test+Automation+Considerations

Educational Seminars On Software Testing

From: Director of Education <Education@iist.org>
Date: Nov 11, 2005 12:43 PM
Subject: Educational Seminars from Int'l Institute for Software Testing


Dear Software Test and Quality Professional,

We will give your test team practical advice free of charge.

Our Free educational seminars are very well received by test and
quality professionals around the country.

These seminars are packed with practical advice and fresh ideas
for the whole test team.

These seminars are taught by Dr. Magdy Hanna, an internationally
recognized speaker and practitioner in Software Testing and
quality assurance.

Nothing to loose, lots to gain. Still not sure? Read what
Other test professionals said about these seminars at:
http://www.testinginstitute.com/seminar/testimonials.php

In accordance with its charter of promoting disciplined
software test practices, the International Institute
for Software Testing is offering a series of educational
seminars around the country. These seminars are offered
free of charge to software test professionals seeking
to improve their testing career.

Do not miss these purely educational opportunities.

OUR PROMISE: NO SALES PITCHES, NO NONSENSE, ONLY EDUCATION


CURRENTLY SCHEDULED SESSIONS
============================

More sessions will be added on a regular basis. Please visit http://www.testinginstitute.org/seminar.php for update.


** San Francisco, CA, December 8, 2005
----------------------------------------
This is a full day free seminar
Morning session: 8:30-12:00, Disciplined Software Testing Practices
Afternoon session: 1:00-4:30, Effective Test Management Practices

** Orlando, FL, January 19, 2006
----------------------------------
This is a full day free seminar
Morning session: 8:30-12:00, Disciplined Software Testing Practices
Afternoon session: 1:00-4:30, Effective Test Management Practices

** Minneapolis, MN, February 17, 2006
-------------------------------------
This is a half day free seminar
Morning session: 8:30-12:00, Disciplined Software Testing Practices

** Washington, DC, April 27, 2006
----------------------------------
This is a half day free seminar
Morning session: 8:30-12:00, Disciplined Software Testing Practice

Seminar outlines and registration information at:
http://www.testinginstitute.org/seminar.php


Testimonials:
This is a world-class event: 98% of past attendees "recommend
this seminar" to their peers

"What a nice surprise...I thought this was just a marketing tool.
The instructor was very detailed in this seminar and makes me
proud to be in the testing profession."

"It was a great session. I was not expecting as much information
in a FREE seminar. I definitely learned new tools to use on my
projects."

"The instructor was absolutely the most dynamic speaker I have
ever heard. I thoroughly enjoyed the seminar. I would love to
attend additional training."

"The fact that the sales pitch wasn't what this was about was
invaluable to make me want to come back for more courses."

"Thank you for organizing such a beneficial event! I'll be able
to apply most of the methods in my everyday work. The methods
provided in this seminar will improve the communications between
business, software engineers and test engineers, and will reduce
the possibility of wrong interpretation of the project's
requirements. All of it leads to minimizing time, resources,
and cost for achieving the desired quality product."

To see more testimonials, visit
http://www.testinginstitute.com/seminar/testimonials.php

Questions? Please call our office at the number below.

==========================================

Department of Education and Professional Development
International Institute for Software Testing
636 Mendelssohn Ave. North
Golden Valley, MN 55427
763-546-0072
http://www.iist.org

History's Worst Software Bugs

Last month automaker Toyota announced a recall of 160,000 of its Prius hybrid vehicles following reports of vehicle warning lights illuminating for no reason, and cars' gasoline engines stalling unexpectedly. But unlike the large-scale auto recalls of years past, the root of the Prius issue wasn't a hardware problem -- it was a programming error in the smart car's embedded code. The Prius had a software bug.

With that recall, the Prius joined the ranks of the buggy computer -- a club that began in 1947 when engineers found a moth in Panel F, Relay #70 of the Harvard Mark 1 system. The computer was running a test of its multiplier and adder when the engineers noticed something was wrong. The moth was trapped, removed and taped into the computer's logbook with the words: "first actual case of a bug being found. 

Read the complete article here... 
 

http://wired.com/news/technology/bugs/0,2924,69355,00.html?tw=wn_tophead_1

 

Fundamentals of Software Testing

 

Objectives of Testing

Finding of Errors - Primary Goal
Trying to prove that software does not work. Thus, indirectly verifying that software meets requirements
Software Testing
Software testing is the process of testing the functionality and correctness of software by running it. Software testing is usually performed for one of two reasons:
(1) defect detection
(2) reliability or Process of executing a computer program and comparing the actual behavior with the expected behavior

What is the goal of Software Testing?
* Demonstrate That Faults Are Not Present
* Find Errors
* Ensure That All The Functionality Is Implemented
* Ensure The Customer Will Be Able To Get His Work Done

Modes of Testing
* Static Static Analysis doesn¡¦t involve actual program execution. The code is examined, it is tested without being executed Ex: - Reviews
* Dynamic In Dynamic, The code is executed. Ex:- Unit testing

Testing methods
* White box testing Use the control structure of the procedural design to derive test cases.
* Black box testing Derive sets of input conditions that will fully exercise the functional requirements for a program.
* Integration Assembling parts of a system

Verification and Validation
* Verification: Are we doing the job right? The set of activities that ensure that software correctly implements a specific function. (i.e. The process of determining whether or not products of a given phase of the software development cycle fulfill the requirements established during previous phase). Ex: - Technical reviews, quality & configuration audits, performance monitoring, simulation, feasibility study, documentation review, database review, algorithm analysis etc
* Validation: Are we doing the right job? The set of activities that ensure that the software that has been built is traceable to customer requirements.(An attempt to find errors by executing the program in a real environment ). Ex: - Unit testing, system testing and installation testing etc

What's a 'test case'?
A test case is a document that describes an input, action, or event and an expected response, to determine if a feature of an application is working correctly. A test case should contain particulars such as test case identifier, test case name, objective, test conditions/setup, input data requirements, steps, and expected results

What is a software error ?
A mismatch between the program and its specification is an error in the program if and only if the specifications exists and is correct.

Risk Driven Testing
What if there isn't enough time for thorough testing?
Use risk analysis to determine where testing should be focused. Since it's rarely possible to test every possible aspect of an application, every possible combination of events, every dependency, or everything that could go wrong, risk analysis is appropriate to most software development projects. This requires judgement skills, common sense, and experience.

Considerations can include:
- Which functionality is most important to the project's intended purpose?
- Which functionality is most visible to the user?
- Which aspects of the application are most important to the customer?
- Which parts of the code are most complex, and thus most subject to errors?
- What do the developers think are the highest-risk aspects of the application?
- What kinds of tests could easily cover multiple functionality?
Whenever there's too much to do and not enough time to do it, we have to prioritize so that at least the most important things get done. So prioritization has received a lot of attention. The approach is called Risk Driven Testing. Here's how you do it: Take the pieces of your system, whatever you use - modules, functions, section of the requirements - and rate each piece on two variables, Impact and Likelihood.


Risk has two components: Impact and Likelihood

Impact
is what would happen if this piece somehow malfunctioned. Would it destroy the customer database? Or would it just mean that the column headings in a report didn't quite line up?

Likelihood
is an estimate of how probable it is that this piece would fail. Together, Impact and Likelihood determine Risk for the piece.


Test Planning

What is a test plan?
A software project test plan is a document that describes the objectives, scope, approach, and focus of a software testing effort. The process of preparing a test plan is a useful way to think through the efforts needed to validate the acceptability of a software product.

Elements of test planning
* Establish objectives for each test phase
* Establish schedules for each test activity
* Determine the availability of tools, resources
* Establish the standards and procedures to be used for planning and conducting the tests and reporting test results
* Set the criteria for test completion as well as for the success of each test

The Structured Approach to Testing

Test Planning
* Define what to test
* Identify Functions to be tested
* Test conditions
* Manual or Automated
* Prioritize to identify Most Important Tests
* Record Document References

Test Design
* Define how to test
* Identify Test Specifications
* Build detailed test scripts
* Quick Script generation
* Documents

Test Execution
* Define when to test
* Build test execution schedule
* Record test results


Bug Overview

What is a software error?
A mismatch between the program and its specification is an error in the Program if and only if the specification exists and is correct.
Example: -
* The date on the report title is wrong
* The system hangs if more than 20 users try to commit at the same time
* The user interface is not standard across programs

Categories of Software errors
* User Interface errors
* Functionality errors
* Performance errors
* Output errors
* documentation errors

What Do You Do When You Find a Bug?
IF A BUG IS FOUND,
* alert the developers that a bug exists
* show them how to reproduce the bug
* ensure that if the developer fixes the bug it is fixed correctly and the fix
* didn't break anything else
* keep management apprised of the outstanding bugs and correction trends

Bug Writing Tips
Ideally you should be able to write bug report clearly enough for a developer to reproduce and fix the problem, and another QA engineer to verify the fix without them having to go back to you, the author, for more information.
To write a fully effective report you must :-
* Explain how to reproduce the problem
* Analyze the error so you can describe it in a minimum number of steps
* Write a report that is complete and easy to understand


Product Test Phase - Product Testing Cycle

Pre-Alpha
Pre-Alpha is the test period during which QA, Information Development and other internal users make the product available for internal testing.
Alpha

Alpha is the test period during which the product is complete and usable in a test environment but not necessarily bug-free. It is the final chance to get verification from customers that the tradeoffs made in the final development stage are coherent.
Entry to Alpha
* All features complete/testable (no urgent bugs or QA blockers)
* High bugs on primary platforms fixed/verified
* 50% of medium bugs on primary platforms fixed/verified
* All features tested on primary platforms
* Alpha sites ready for install
* Final product feature set Determined

Beta
Beta is the test period during which the product should be of "FCS quality" (it is complete and usable in a production environment). The purpose of the Beta ship and test period is to test the company's ability to deliver and support the product (and not to test the product itself). Beta also serves as a chance to get a final "vote of confidence" from a few customers to help validate our own belief that the product is now ready for volume shipment to all customers.
Entry to Beta

* At least 50% positive response from Alpha sites
* All customer bugs addressed via patches/drops in Alpha
* All bugs fixed/verified
* Bug fixes regression tested
* Bug fix rate exceeds find rate consistently for two weeks
* Beta sites ready for install

GM (Golden Master)
GM is the test period during which the product should require minimal work, since everything was done prior to Beta. The only planned work should be to revise part numbers and version numbers, prepare documentation for final printing, and sanity testing of the final bits.
Entry to Golden Master

* Beta sites declare the product is ready to ship
* All customer bugs addressed via patches/drops in Beta
* All negative responses from sites tracked and evaluated
* Support declares the product is supportable/ready to ship
* Bug find rate is lower than fix rate and steadily decreasing

FCS (First Customer Ship)
FCS is the period which signifies entry into the final phase of a project. At this point, the product is considered wholly complete and ready for purchase and usage by the customers.
Entry to FCS

* Product tested for two weeks with no new urgent bugs
* Product team declares the product is ready to ship

================================

Author: vinod
http://www.software-engineer.org/article_read.php?article_id=20000240&PHPSESSID=adaab73798932bce08969e323d53cdc1

 

Thread Based Integration Testing

 

Introduction

Our organization has recently completed the development of a large-scale command and control system through the implementation and formal qualification phases of the project. This development involved over eighty software engineers developing roughly 1.5 million source lines of code using multiple languages and platforms. In order to deliver the product within the projected schedule, parallel development and rapid integration occurred over many related software functional areas. To facilitate the decomposition of our design into manageable components we chose the concept of a “functional thread” as the elementary building block for integration. In this context, a “functional thread” is defined as a logical execution sequence through a series of interfacing software components resulting from or ending in the receipt of a message, event or operator interaction.

Threads not only serve as the basis for integration, they also tend to drive the entire software development effort from scheduling to status reporting. Each thread itself represents a microcosm of the system in that each has a documented definition and general execution path, an internal design and an associated test. Thread definition intends to communicate functional background and execution details between developers and from developers to testers. More importantly, the desired independence of threads supports incremental integration and system testing while the corresponding thread definition substantiates the results. Finally, since all system development activity progresses in relation to threads, management has an accurate method of judging the status of individual tasks, functional areas and requirements.

Threads

Keeping the goals of iterative development and testing in mind, each thread has its own lifecycle with autonomous states and a formal process for state transitions (see Figure 1). Individual team leaders usually decompose general requirements into groups of threads at the beginning of formal, six month software builds and assign threads to developers. Developers maintain ownership of their threads and are responsible for documenting a scenario under which an integrator can verify the basic functionality, providing rudimentary definition to the thread. Following implementation and unit test, the developer releases the corresponding software components to a daily integration build, at which point the thread enters a “testable” state. After verifying the functionality in the integration build, the developer marks the thread “ready” for an integrator who performs more extensive testing and eventually “integrates” the thread and corresponding software components into the system. At the end of each formal build, a team of key engineers in conjunction with quality assurance checks all threads against requirements as a regression test and “finalizes” those threads which pass.

While the development team originally tracked threads manually, we quickly developed a shared database application to serve as a central repository for thread development, maintenance and tracking. The database provides a formal mechanism for defining and documenting threads, changing thread status and reporting status to project management. Moreover, the database manages references between threads: threads can serve as preconditions to other threads and developers may incorporate thread test steps from previous threads. Most importantly, the interface helps enforce the process by demonstrating the autonomy of thread status and establishing clearly defined responsibilities among developers and testers.

Thread Test Steps

Thread test steps and other background information from the database serve as a contract between developers and integrators. Integrators use thread test steps as a simple scenario to identify the scope of a thread rather than as a rigid test case that may only rubber-stamp a developer’s unit test. Consequently, the integrators are responsible for developing several execution scenarios within the boundaries of the thread and applying appropriate testing mechanisms such as known exceptional cases and boundary checking. Furthermore, the integration team often stresses exercising subsystem interfaces during integration testing, which was an area that thread steps often overlooked.

In addition to helping formalize the implementation process, the thread testing approach standardizes the integration testing process as well. As a result, the number of detected coding errors increased almost 250 percent over three formal builds after thread testing had been introduced. Although errors attributable to integration doubled during the first formal build during which our group used threads, that number has subsequently dropped to almost fifty percent below the level at which we started using threads.

While thread-based development certainly contributes greatly to the main goals of early, rapid integration and iterative development, we have also identified several potential areas of further process improvement. Perhaps most notably, developers and testers shared concerns that thread scope lacked uniformity among subsystems. At times, thread definitions were far too specific and a conscientious integrator could verify the basic functionality in fewer steps than the developer identified. Likewise, developers sometimes defined threads at too high a level, requiring the integrator to seek further information from the developer to ensure a meaningful test. A thread review process, perhaps as part of a design walk through, may answer this problem. Likewise, we recommend requiring completion of a code walk through as a prerequisite to thread completion due to the implications of walk through initiated design and code changes.

Thread Maintenance

A related area of improvement is thread maintenance. While the process encouraged (and the database supported) threads referencing other threads, maintaining consistency was not always an easy task. Furthermore, while software that composes a thread often changes after a thread has been integrated, there is no formal update process for the thread. The changes to process here are obvious and one could modify the tool to help enforce these concerns. For example, the tool would benefit from the ability to attach references to source code units so that changes to code might trigger the need for associated thread changes.

In this project the thread process focused on the integration activities rather than the full development lifecycle. This is certainly the main difference between our thread-based approach and use-case analysis. The thread database requires references to user interface specifications where applicable, but the process did not link the thread directly to the requirements database. Thus software testing and overall system testing were somewhat disjoint in that system testers found it difficult to use the thread database as a reference when creating test cases. Though it might be desirable to shift thread definition to the requirements analysis phases of the project, such analysis usually occurs at a higher level than what we had used for our threads and almost always span subsystem boundaries. Instead we suggest a more hierarchical approach to thread definition rooted in requirement-based parent threads. This would directly link the software thread repository to system requirements and better facilitate a similar iterative approach to system-wide testing. Finally, by linking threads directly to requirements, project management would have better insight about the status of entire requirements.

Since threads drove the software efforts and status, developers viewed threads as the most visible formal process in place. The simplicity of the process, accurate status and integration efficiency contributed to the development team’s acceptance of the process and enthusiasm to suggest improvements. In addition, the empirical results suggest that the introduction of thread-based testing exposed design and coding errors earlier and attributed fewer errors to the integration process itself, probably due to the enhanced communication between developers and testers. In short, our method appears to have synchronized the notion of task completion among developers, testers and management.

Summary

Thread-based integration testing played a key role in the success of this software project. At the lowest level, it provided integrators with better knowledge of the scope of what to test, in effect a contract between developers and testers. At the highest level, it provided a unified status tracking method and facilitated an agreement between management and the developers as to what would be delivered during each formal build. Furthermore, instead of testing software components directly, it required integrators to focus on testing logical execution paths in the context of the entire system. Because of this, it strongly supported the goals of early, rapid integration coupled with an iterative development approach. In summary, the thread approach resulted in tangible executable scenarios driving development and integration while the autonomous, well-defined thread states strengthened the use of threads as an accurate method of scheduling and tracking status.

Testing for Zero bugs

The Software Quality Myth

A widely accepted premise on software quality is that software is so complex (in combinatorial terms) that it is impossible to have defect free software. We often hear maxims like "there's always one more bug", and "software testing can reveal the existence of bugs, but never prove their absence".

While the above maxims may be true, I'm afraid they tend to lead us to a state of mind where we accept them as an inevitable evil. If there's no way to make software clean - why bother.

Having some prior experience with software testing, I'm certain that we can do much better than we do today. Once we do this right, the results would pleasantly surprise us.

---

Conventional testing: How we test software?

Looking at the ways we test software, we see the following methods:

• Known scenario replay (test suites, regression tests)
• Random early exposure (Campus alphas, selected customer betas)

The known scenario replay is the single most commonly used method to test software. Unfortunately, it is the least effective method to uncover bugs as proven by the large number of bugs uncovered in later stages.

Regression tests and test suites are necessary but insufficient. They're a good way for conducting sanity checking and ensuring that popular and commonly compiled code runs correctly. However, they have two striking flaws:

• Coverage is extremely limited. When you run the same suite so many times, obviously your bugs tend to hide elsewhere.
  
  
• It is difficult to track bugs in case of failure. Test suites tend to be big pieces of code. When something goes wrong, we apply some further trial runs and search techniques until the problem is narrowed down to a single routine or line of source code.

Early exposure like alpha (and beta) testing has the advantage that it is much more random than the known-scenario replay. It provides more "real world" coverage, but it has its own flaws:

• Since it is an informal testing method, reproducibility is a problem (e.g asking a beta customer: what exactly did you do to experience the problem?")
• It relies on people's good will to investigate problems as they occur, and report bugs accurately and with enough detail when they are found.
• It suffers for a small scope (time, number of machines, and people employed) compared to the real installed base and its usage patterns.
• At least the Alpha part doesn't really emulate our customer environment: our environment is far from heterogenic: almost no other vendors' machines (Sun, HP, IBM, Mac, PCs) exist on campus.

Fortunately, there is a complementary testing method that covers the above flaws well.

---

Monkeys at work: Random Testing

It is said that if you give a zillion monkeys keyboards and let them type long enough, one of them would eventually produce (insert your favorite magnum opus here). Finding bugs is probably much easier than writing magnum opii. If you think this is absurd, just substitute the word "monkeys" with "customers".

For years we have been sending our software to much less than a zillion customers, and yet, without exception, they eventually hit hundreds of undiscovered bugs.

Optimization imperative #1 calls for applying zillions of computer cycles before shipment to try and beat the customers in the race to uncover the bugs. This is what random testing is all about. This is also obvious. The magic is in the details.

---

Constrained Random Testing: a zillion monkeys, optimized

Since the combinatorial space of software is so huge we would like the proverbial monkeys to be constrained in some way and not purely random. To give an example: if we had our monkeys test UNIX for us, we would want them to type stuff like ls, make, cc etc. rather than having them type stuff like %^3gkl'$#*(&% (*).

``Elementary,'' you may say, but read on.

---

A proof by example: It just works!

Before going into the details of Constrained Random Testing, let me state that from my experience applying this technique, to one problem space, it works far better than any other conventional testing method I've seen.

I used to work at the National Semiconductor microprocessor design center in Tel Aviv (NSTA) where I was a member of the Compilers team who wrote the compilers for all the 32000 Series of microprocessors.

For several years, our compilers were buggy as hell. Having worked closely with hardware engineers, we were urged to test the compilers "like hardware is tested", using random "vectors" of input. Once we were on the right track in our tought process things started to improve fast. It took one engineer about 4 months to come with a prototype for random compiler testing. He was generating random IR (Intermediate Representation) because it was easier to do than generating high-level code and we just needed a proof of concept. As a result we were testing only the back-end (Optimizer, Code generator, assembler, linker).

The introduction of random testing practically eliminated user bug reports on released back ends. At a certain point, we couldn't believe it ourselves, so we conducted an experiment by running the random program generator (it used to be called RIG, for Random IR Generator) and was implemented by Avi Bloch and Amit Matatia (see acknowledgments) on a previous release of the compiler. To our amazement, RIG was able to find over half of all the bugs reported by customers on the code generator in just one night of runtime.

Thanks to RIG, the GNX Compilers for the 32000 processor family have matured in a very short period to become one of the most reliable in the industry; I remember compiling an early version of perl (I think it was perl 2.0) with full optimizations and passing the whole test suite on a Sequent Balance (a big 32032-CPU SMP machine), while the SunOS and the HP/UX compilers I used for comparison weren't anywhere near this quality at that time (mind you, that was way back, in 1990 or so).

Based on this personal experience, I have no doubt this method is well worth pursuing here.

---

Testing a Compiler: CRT Outline

Here's the skeleton of RIG:

Loop:

• Generate a random program subject to constraints
• Compile it
• Run it
• Check that the results make sense:
  • if they do, discard of the program
  • if not, save the program and results for later human inspection

Generating a random program is done using recursive descent on the grammar of the language, while applying constraints at every node on the random generator (explained below). To give a simple example: pick an operand at random, check its arity, generate N random operands to operate on. Each operand can be either a constant or an arbitrary randomly generated new expression. etc.

---

Constraint Magic: making a random program behave

The outline sounds simple enough, but a few problems immediately come to mind:

• How can you ensure that a randomly generated program terminates?
• How can you ensure that a randomly generated program doesn't generate an exception?
• How can you ensure that a perfectly "safe" optimization won't change the semantics of the program (e.g. use of an undefined variable, the behavior of which is undefined)

This is where the constraints come into play. The embedded constraints are what turns the method from a pure theoretical play into a practical and effective testing method.

• To ensure termination, we artificially inject an independent counter into every randomly generated loop or recursive function call, if a configurable limit is exceeded, we just break out of the loop. Not perfect, indeed, but simple, straightforward, and does the job.

• As for exceptions, there are two approaches: one is to simply allow them, if a randomly picked divisor happens to be zero, so be it. The output may be partial, but still deterministic. The other approach (if exceptions happen too often) is to regenerate those expressions that cause the exceptions, or to ensure by construction that they always fall within a certain range of values.

  For example, we ensure that constant divisors are never zero, and that variable divisors are checked at run time (if they are zero don't divide). Likewise we may add a check before array accesses for legal indexes into a pre-generated array. From experience, the second approach is what you want in 99% of the cases, and again, it works well.

• To make sure the program has outputs (so we can inspect its runtime results) we simply put a hook to print all the randomly generated variables and constants of the program from a customized exit() routine that is linked with the program.

• Likewise, to ensure there's no use of undefined variables, we simply initialize all of them (with random values of course) just before we jump to main().
  

This is in essence what the constraints are all about.

---

Closing the loop: proving correctness

But then there's another more fundamental question:

• If the program is randomly generated, (i.e. not known in advance) how can you predict its output, in order to verify that it ran correctly?

It turns out that even though the answer to the third question is "You can't", still, from a practical point of view, there's a nice solution to this. Not only it is simple, but it was also empirically proven to work very well.

Solution: Generate a reference output using another compiler or interpreter for the same language. E.g. for C, the reference may be a most vanilla compilation (without any optimizations) by a widely deployed and stable compiler like GNU cc (gcc). This can be even done on a different vendor's system.

Actually, for most cases, you don't even need an additional compiler: You may generate multiple outputs using the same compiler under test, each time with different compilation options. For example: If the result with optimization is different than the one without it, bingo: you've found a bug in the optimizer.

---

Practice & experience: The importance of space/time tuning

The constraints mentioned above are just part of the story. To be effective and efficient, the random program generator should be space/time tuned, for example: Testing a small array for an unsigned index wrap-around case is effective as checking a big array and is far less consuming in time and space. Thus: elements like the maximum size of a randomly generated array, maximum number of elements in a structure, or the maximum depth of an expression should all be configurable via a configuration file.

Results (in terms of detected bugs per unit of testing time) can change dramatically by fine tuning of these space/time constraint parameters. The general guideline is: strive to use constraints that will create the smallest/simplest case to exhibit the problem.

Some golden rules:

• Don't generate big data structures.
• Don't generate big programs, loops, or routines
• For every possible range of values, use some bias towards extremum and "interesting" values (MAXINT, 1, 0, -1, last index of an array) as opposed to a uniform distribution of values.
• Think hard about the constraints, let the random generator do the rest
• For every generated program, run it against as many cases as possible (e.g. many possible compiler options) to amortize the generation overhead, and leverage the reference results over many test cases.

From my experience, all compiler bugs can be narrowed down and reproduced in a very small example. Come to think of it, This is exactly what makes random testing of compilers work so well. Also, the smaller the example, the easier it is to investigate and fix. This is where tuning pays big: if you can generate 100,000 tiny programs per night you'll be much more effective covering the compiler and fixing the bugs than if you generate 1000 larger programs per night.

---

More Advice

Start with simple expressions, including all types and all possible cast and type conversions, these are easy to test and are a first step in a CRT implementation that is natural to start with and build upon.

Pick a very good random number generator. If you don't and if you don't have much variability in the types of nodes that you randomly generate, your programs will tend to find the same bug multiple times. There are practical ways to minimize this: like changing the configuration parameters once a bug is found (and until the bug is fixed) but this requires further resources and effort.

Generate random C rather than random IR. You cannot compile proprietary formats with a reference compiler (not the one you're testing). You also get to test the language front ends in addition to the back end.

It may be easier to generate IR and upwardly generate high-level constructs from it. This is certainly a sensible strategy, especially in case the mapping between IR and C is one to one. even if not, this will enable testing Fortran with almost no additional effort (since we already have these "reverse compilers").

Generating test cases, running them, and comparing results normally take less time than many compilation with many options, so pick compilation cases that are as different as possible of each other to get better coverage. Also: try to combine several compilation options with each run (i.e. many optimizations together, vs. a vanilla compilation) to achieve good coverage of the compiler in as few compilations as possible.

Jumbo tip: An excellent way of tuning the constraints and the random program generator is to basic-block profile the compiler itself and see what parts of source code are not being exercised by the randomly generated programs. Then, tune the random generator a bit more. In other words, inject some white-box style testing into the random black-box approach.

---

By ariel faigon
http://www.yendor.com/testing

White Box Testing

Definition of White Box Testing - A software testing technique whereby explicit knowledge of the internal workings of the item being tested are used to select the test data.

Unlike black box testing, white box testing uses specific knowledge of programming code to examine outputs. The test is accurate only if the tester knows what the program is supposed to do. He or she can then see if the program diverges from its intended goal. White box testing does not account for errors caused by omission, and all visible code must also be readable.

Contrary to black-box testing, software is viewed as a white-box, or glass-box in white-box testing, as the structure and flow of the software under test are visible to the tester.

Testing plans are made according to the details of the software implementation, such as programming language, logic, and styles. Test cases are derived from the program structure. White-box testing is also called glass-box testing, logic-driven testing or design-based testing.

There are many techniques available in white-box testing, because the problem of intractability is eased by specific knowledge and attention on the structure of the software under test. The intention of exhausting some aspect of the software is still strong in white-box testing, and some degree of exhaustion can be achieved, such as executing each line of code at least once (statement coverage), traverse every branch statements (branch coverage), or cover all the possible combinations of true and false condition predicates (Multiple condition coverage).

Control-flow testing, loop testing, and data-flow testing, all maps the corresponding flow structure of the software into a directed graph. Test cases are carefully selected based on the criterion that all the nodes or paths are covered or traversed at least once. By doing so we may discover unnecessary "dead" code -- code that is of no use, or never get executed at all, which can not be discovered by functional testing.

In mutation testing, the original program code is perturbed and many mutated programs are created, each contains one fault. Each faulty version of the program is called a mutant. Test data are selected based on the effectiveness of failing the mutants. The more mutants a test case can kill, the better the test case is considered. The problem with mutation testing is that it is too computationally expensive to use. The boundary between black-box approach and white-box approach is not clear-cut. Many testing strategies mentioned above, may not be safely classified into black-box testing or white-box testing. It is also true for transaction-flow testing, syntax testing, finite-state testing, and many other testing strategies not discussed in this text. One reason is that all the above techniques will need some knowledge of the specification of the software under test. Another reason is that the idea of specification itself is broad -- it may contain any requirement including the structure, programming language, and programming style as part of the specification content.

We may be reluctant to consider random testing as a testing technique. The test case selection is simple and straightforward: they are randomly chosen. Study indicates that random testing is more cost effective for many programs. Some very subtle errors can be discovered with low cost. And it is also not inferior in coverage than other carefully designed testing techniques. One can also obtain reliability estimate using random testing results based on operational profiles. Effectively combining random testing with other testing techniques may yield more powerful and cost-effective testing strategies.