DZone
Thanks for visiting DZone today,
Edit Profile
  • Manage Email Subscriptions
  • How to Post to DZone
  • Article Submission Guidelines
Sign Out View Profile
  • Post an Article
  • Manage My Drafts
Over 2 million developers have joined DZone.
Log In / Join
Refcards Trend Reports
Events Video Library
Refcards
Trend Reports

Events

View Events Video Library

Zones

Culture and Methodologies Agile Career Development Methodologies Team Management
Data Engineering AI/ML Big Data Data Databases IoT
Software Design and Architecture Cloud Architecture Containers Integration Microservices Performance Security
Coding Frameworks Java JavaScript Languages Tools
Testing, Deployment, and Maintenance Deployment DevOps and CI/CD Maintenance Monitoring and Observability Testing, Tools, and Frameworks
Culture and Methodologies
Agile Career Development Methodologies Team Management
Data Engineering
AI/ML Big Data Data Databases IoT
Software Design and Architecture
Cloud Architecture Containers Integration Microservices Performance Security
Coding
Frameworks Java JavaScript Languages Tools
Testing, Deployment, and Maintenance
Deployment DevOps and CI/CD Maintenance Monitoring and Observability Testing, Tools, and Frameworks

Generative AI has transformed nearly every industry. How can you leverage GenAI to improve your productivity and efficiency?

SBOMs are essential to circumventing software supply chain attacks, and they provide visibility into various software components.

Related

  • Handling Concurrent Data Loads in Delta Tables
  • Handling Dynamic Data Using Schema Evolution in Delta
  • Challenges With Traditional Data Sharing and Emergence of Delta Sharing to the Rescue
  • Autoloader to Keep Delta Lake Hot With Data

Trending

  • The Shift to Open Industrial IoT Architectures With Data Streaming
  • Micro Frontends to Microservices: Orchestrating a Truly End-to-End Architecture
  • The Battle of the Frameworks: Choosing the Right Tech Stack
  • Load Testing Essentials for High-Traffic Applications

Debugging Step by Step – Delta Debugging

By 
Istvan Forgacs user avatar
Istvan Forgacs
·
Feb. 19, 14 · Interview
Likes (0)
Comment
Save
Tweet
Share
16.9K Views

Join the DZone community and get the full member experience.

Join For Free

A Cambridge University study states that software bugs cost the global economy $312 billion per year. Bug hunting is a difficult task. As Brian W. Kernighan wrote: “Debugging is twice as hard as writing the code in the first place. Therefore, if you write the code as cleverly as possible, you are, by definition, not smart enough to debug it.” It's unfortunately true. Several times even talented developers are blocked to find bugs. In the following articles "Debugging Step by Step ..." we give some pieces of advice to ease this task.

Let’s assume we have a bug. What is the first step? It depends... Let’s see an example. We implemented a Quicksort algorithm and test it with the numbers:

4, 12, 9, 14, 3, 10, 17, 11, 8, 7, 4, 1, 6, 19, 5, 21, 2, 3

The result is:

1, 3, 2, 5, 3, 4, 4, 6, 7, 8, 9, 10, 11, 12, 14, 17, 19, 21

Thus the test failed. What to do now? One of the possibilities is to start debugging. However, it is not a good idea. Why? Because the execution contains too many steps which is difficult to follow. The number of execution steps is 670, and we should analyze a lot of them until we find the bug.

Delta debugging is an input reduction method resulting in two input sets:

  • one input reveals the bug
  • the other doesn't

for which the difference is minimal, i.e. in the second input only one number is missing from the first one.

There are quite a few manual methods for minimizing the input. If our input is homogeneous, then simple halving may work. The method is simple, after arranging the input into two possibly same size lists, we execute the code, and if one of them is a failure-induced input, then we select it. We keep halving until the method works. When it doesn't, we can reduce the remaining input removing elements one by one. Let's do it now.

Example

Step 1. In our example the halved input is:  4, 12, 9, 14, 3, 10, 17, 11, 8 - getting the   output: 3, 12,                     4, 8, 9, 10, 11, 14, 17, i.e. clearly faulty.

Step 2. The next input is:  4, 12, 9, 14 - for which the output is correct: 4, 9, 12, 14.

Step 3. We try the other half, which is 3, 10, 17, 11, 8, obtaining the output: 3, 8, 10, 11, 17  - again                      correct.

Step 4. Our next output is the reduction of our last failure-induced input by cutting the last two                             numbers:  4, 12, 9, 14, 3, 10, 17. The result is also erroneous: 4, 10, 9, 12, 3, 14, 17.

Cutting any elements the output remains correct, thus our minimized input is :   4, 12, 9, 14, 3, 10, 17. For this test the number of execution steps is 192, less than 30% of the original.

However, the input we obtained is a local minimum, and in some cases we are able to minimize the failure-induced input just thinking a little bit.  Consider the output for the first test again:

1, 3, 2, 5, 3, 4, 4, 6, 7, 8, 9, 10, 11, 12, 14, 17, 19, 21

We can see that apart from the sub-result: 3, 2, 5, 3, 4, the result is correct. Thus we select these numbers from the input set: 4, 3, 5, 2, 3 and it works since the result still contains the bug: 3, 3, 4, 2, 5. No further reduction can be achieved by this way of thinking, though it's not a global minimum either. Nevertheless, the number of steps is reduced to 139, i.e. 20% of the original test.

Returning to our original systematic method and removing the first number 4, our input: 3, 5, 2, 3 - we obtain the faulty 3, 3, 2, 5 - which is the minimum failure-induced input resulting in 111 execution steps and 83% reduction.

And how big the time saving of this minimization is? We don't know. However, if you help us by fixing the bug, we can give the answer. The faulty version of Quicksort is below. If your birthday is in months 1-6, use the original, otherwise the minimized input. Just drop me ([email protected]) a mail with the fixed line(s), the input used and the time spent on fixing (in minutes). I publish the results on our website http://4dsoft.eu/blog and a subsequent article here. Thank you for your cooperation.

Conclusion

Delta debugging is a divide and conquer method by which our original debugging task is simplified by minimizing the input. Debugging is then performed on the simpler code trace.

Our experiences proved that the total bug finding time is largely reduced by applying delta debugging. Our input is sometimes huge 100,000+ lines of Java code, delta debugging is absolutely essential to find bugs in this environment. 

Quicksort with bug

import java.io.*;
import java.util.*;

public class QuickSort
{
	public static void quicksort(int numbers[], int low, int high) {
	    int i = low, j = high;
	    // Get the pivot element from the middle of the list
	    int pivot = numbers[low + (high-low)/2];

	    // Divide into two lists
	    while (i <= j) {
	      while (numbers[i] < pivot) {
	        i++;
	      }
	      while (numbers[j] > pivot) {
	        j--;
	      }
	      if (i <= j) {
	    	  exchange(numbers, i, j);
	      }
	      i++;
	      j--;
	    }
	    // Recursion
	    if (low < j)
	      quicksort(numbers, low, j);  //low
	    if (i < high)                
	      quicksort(numbers, i, high);
	  }

	  private static void exchange(int numbers[], int i, int j) {
	    int temp = numbers[i];
	    numbers[i] = numbers[j];
	    numbers[j] = temp;
	    int k = 1;
	  }
	
	public static void main(String argv[])
   {
		int A[] = {4, 12, 9, 14, 3, 10, 17, 11, 8, 7, 4, 1, 6, 19, 5, 21, 2, 3}; 
		
//		minimized failure-induced input
//		int A[] = {3, 5, 2, 3};  
		
		quicksort(A, 0, A.length - 1);   

		for (int i=0 ; i < A.length ; i++) System.out.print(A[i] + " ");
		System.out.println();
   }
DELTA (taxonomy)

Opinions expressed by DZone contributors are their own.

Related

  • Handling Concurrent Data Loads in Delta Tables
  • Handling Dynamic Data Using Schema Evolution in Delta
  • Challenges With Traditional Data Sharing and Emergence of Delta Sharing to the Rescue
  • Autoloader to Keep Delta Lake Hot With Data

Partner Resources

×

Comments

The likes didn't load as expected. Please refresh the page and try again.

ABOUT US

  • About DZone
  • Support and feedback
  • Community research
  • Sitemap

ADVERTISE

  • Advertise with DZone

CONTRIBUTE ON DZONE

  • Article Submission Guidelines
  • Become a Contributor
  • Core Program
  • Visit the Writers' Zone

LEGAL

  • Terms of Service
  • Privacy Policy

CONTACT US

  • 3343 Perimeter Hill Drive
  • Suite 100
  • Nashville, TN 37211
  • [email protected]

Let's be friends: