1 of 76

Software Debugging

CS 3240 - Advanced Software Development

​

​

CS 3240

2 of 76

“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.”

​

Brian Kernighan

CS 3240

3 of 76

Today

  • Failure simplification
  • Finding likely culprits

CS 3240

4 of 76

Today

  • Failure simplification
  • Finding likely culprits

Key insight: process is experimental but

it can be systematic

CS 3240

5 of 76

Ok… so your program failed on this input

http://joannabefree.blogspot.com/2019/01/a-long-way-to-go-back.html

CS 3240

6 of 76

Ok… so your HTML parser crashed on this input

<td align=left valign=top>

​

<SELECT NAME="op sys" MULTIPLE SIZE=7>

​

<OPTION VALUE="All">All<OPTION VALUE="Windows 3.1">Windows 3.1<OPTION VALUE="Windows 95">Windows 95<OPTION VALUE="Windows 98">Windows 98<OPTION

VALUE="Windows ME">Windows ME<OPTION VALUE="Windows 2000">Windows 2000<OPTION VALUE="Windows NT">Windows NT<OPTION VALUE="Mac System 7">Mac

System 7<OPTION VALUE="Mac System 7.5">Mac System 7.5<OPTION VALUE="Mac System 7.6.1">Mac System 7.6.1<OPTION VALUE="Mac System 8.0">Mac System

8.0<OPTION VALUE="Mac System 8.5">Mac System 8.5<OPTION VALUE="Mac System 8.6">Mac System 8.6<OPTION VALUE="Mac System 9.x">Mac System

9.x<OPTION VALUE="MacOS X">MacOS X<OPTION VALUE="Linux">Linux<OPTION VALUE="BSDI">BSDI<OPTION VALUE="FreeBSD">FreeBSD<OPTION

VALUE="NetBSD">NetBSD<OPTION VALUE="OpenBSD">OpenBSD<OPTION VALUE="AIX">AIX<OPTION VALUE="BeOS">BeOS<OPTION VALUE="HP-UX">HP-UX<OPTION

VALUE="IRIX">IRIX<OPTION VALUE="Neutrino">Neutrino<OPTION VALUE="OpenVMS">OpenVMS<OPTION VALUE="OS/2">OS/2<OPTION VALUE="OSF/1">OSF/1<OPTION

VALUE="Solaris">Solaris<OPTION VALUE="SunOS">SunOS<OPTION VALUE="other">other</SELECT>

​

</td>

​

<td align=left valign=top>

​

<SELECT NAME="priority" MULTIPLE SIZE=7>

​

<OPTION VALUE="--">--<OPTION VALUE="P1">P1<OPTION VALUE="P2">P2<OPTION VALUE="P3">P3<OPTION VALUE="P4">P4<OPTION VALUE="P5">P5</SELECT>

​

</td>

​

<td align=left valign=top>

​

<SELECT NAME="bug severity" MULTIPLE SIZE=7>

​

<OPTION VALUE="blocker">blocker<OPTION VALUE="critical">critical<OPTION VALUE="major">major<OPTION VALUE="normal">normal<OPTION

VALUE="minor">minor<OPTION VALUE="trivial">trivial<OPTION VALUE="enhancement">enhancement</SELECT>

​

</tr>

​

</table>

http://joannabefree.blogspot.com/2019/01/a-long-way-to-go-back.html

CS 3240

7 of 76

Ok… so your HTML parser crashed on this input

Hypothesis Generation

  • Maybe is the load of the 10,000 tokens?
  • Maybe some of the specific OPTIONS?
  • Maybe is the sequence of SELECT and OPTIONS?
  • Maybe is the table? Or the table alignments?
  • Or ...?

<td align=left valign=top>

​

<SELECT NAME="op sys" MULTIPLE SIZE=7>

​

<OPTION VALUE="All">All<OPTION VALUE="Windows 3.1">Windows 3.1<OPTION VALUE="Windows 95">Windows 95<OPTION VALUE="Windows 98">Windows 98<OPTION

VALUE="Windows ME">Windows ME<OPTION VALUE="Windows 2000">Windows 2000<OPTION VALUE="Windows NT">Windows NT<OPTION VALUE="Mac System 7">Mac

System 7<OPTION VALUE="Mac System 7.5">Mac System 7.5<OPTION VALUE="Mac System 7.6.1">Mac System 7.6.1<OPTION VALUE="Mac System 8.0">Mac System

8.0<OPTION VALUE="Mac System 8.5">Mac System 8.5<OPTION VALUE="Mac System 8.6">Mac System 8.6<OPTION VALUE="Mac System 9.x">Mac System

9.x<OPTION VALUE="MacOS X">MacOS X<OPTION VALUE="Linux">Linux<OPTION VALUE="BSDI">BSDI<OPTION VALUE="FreeBSD">FreeBSD<OPTION

VALUE="NetBSD">NetBSD<OPTION VALUE="OpenBSD">OpenBSD<OPTION VALUE="AIX">AIX<OPTION VALUE="BeOS">BeOS<OPTION VALUE="HP-UX">HP-UX<OPTION

VALUE="IRIX">IRIX<OPTION VALUE="Neutrino">Neutrino<OPTION VALUE="OpenVMS">OpenVMS<OPTION VALUE="OS/2">OS/2<OPTION VALUE="OSF/1">OSF/1<OPTION

VALUE="Solaris">Solaris<OPTION VALUE="SunOS">SunOS<OPTION VALUE="other">other</SELECT>

​

</td>

​

<td align=left valign=top>

​

<SELECT NAME="priority" MULTIPLE SIZE=7>

​

<OPTION VALUE="--">--<OPTION VALUE="P1">P1<OPTION VALUE="P2">P2<OPTION VALUE="P3">P3<OPTION VALUE="P4">P4<OPTION VALUE="P5">P5</SELECT>

​

</td>

​

<td align=left valign=top>

​

<SELECT NAME="bug severity" MULTIPLE SIZE=7>

​

<OPTION VALUE="blocker">blocker<OPTION VALUE="critical">critical<OPTION VALUE="major">major<OPTION VALUE="normal">normal<OPTION

VALUE="minor">minor<OPTION VALUE="trivial">trivial<OPTION VALUE="enhancement">enhancement</SELECT>

​

</tr>

​

</table>

CS 3240

8 of 76

Failure simplification / isolation

​

Program

Test

Refine

Hypotheses

Pass

Fails

CS 3240

9 of 76

Ok… so your parser crashed on this input

Test hypothesis

  • Or the table alignments?

<td align=left valign=top>

​

<SELECT NAME="op sys" MULTIPLE SIZE=7>

​

<OPTION VALUE="All">All<OPTION VALUE="Windows 3.1">Windows 3.1<OPTION VALUE="Windows 95">Windows 95<OPTION VALUE="Windows 98">Windows 98<OPTION

VALUE="Windows ME">Windows ME<OPTION VALUE="Windows 2000">Windows 2000<OPTION VALUE="Windows NT">Windows NT<OPTION VALUE="Mac System 7">Mac

System 7<OPTION VALUE="Mac System 7.5">Mac System 7.5<OPTION VALUE="Mac System 7.6.1">Mac System 7.6.1<OPTION VALUE="Mac System 8.0">Mac System

8.0<OPTION VALUE="Mac System 8.5">Mac System 8.5<OPTION VALUE="Mac System 8.6">Mac System 8.6<OPTION VALUE="Mac System 9.x">Mac System

9.x<OPTION VALUE="MacOS X">MacOS X<OPTION VALUE="Linux">Linux<OPTION VALUE="BSDI">BSDI<OPTION VALUE="FreeBSD">FreeBSD<OPTION

VALUE="NetBSD">NetBSD<OPTION VALUE="OpenBSD">OpenBSD<OPTION VALUE="AIX">AIX<OPTION VALUE="BeOS">BeOS<OPTION VALUE="HP-UX">HP-UX<OPTION

VALUE="IRIX">IRIX<OPTION VALUE="Neutrino">Neutrino<OPTION VALUE="OpenVMS">OpenVMS<OPTION VALUE="OS/2">OS/2<OPTION VALUE="OSF/1">OSF/1<OPTION

VALUE="Solaris">Solaris<OPTION VALUE="SunOS">SunOS<OPTION VALUE="other">other</SELECT>

​

</td>

​

<td align=left valign=top>

​

<SELECT NAME="priority" MULTIPLE SIZE=7>

​

<OPTION VALUE="--">--<OPTION VALUE="P1">P1<OPTION VALUE="P2">P2<OPTION VALUE="P3">P3<OPTION VALUE="P4">P4<OPTION VALUE="P5">P5</SELECT>

​

</td>

​

<td align=left valign=top>

​

<SELECT NAME="bug severity" MULTIPLE SIZE=7>

​

<OPTION VALUE="blocker">blocker<OPTION VALUE="critical">critical<OPTION VALUE="major">major<OPTION VALUE="normal">normal<OPTION

VALUE="minor">minor<OPTION VALUE="trivial">trivial<OPTION VALUE="enhancement">enhancement</SELECT>

​

</tr>

​

</table>\

<td align=left valign=top>

​

<SELECT NAME="op sys" MULTIPLE SIZE=7>

​

<OPTION VALUE="All">All<OPTION VALUE="Windows 3.1">Windows 3.1<OPTION VALUE="Windows 95">Windows 95<OPTION VALUE="Windows 98">Windows 98<OPTION

VALUE="Windows ME">Windows ME<OPTION VALUE="Windows 2000">Windows 2000<OPTION VALUE="Windows NT">Windows NT<OPTION VALUE="Mac System 7">Mac

System 7<OPTION VALUE="Mac System 7.5">Mac System 7.5<OPTION VALUE="Mac System 7.6.1">Mac System 7.6.1<OPTION VALUE="Mac System 8.0">Mac System

8.0<OPTION VALUE="Mac System 8.5">Mac System 8.5<OPTION VALUE="Mac System 8.6">Mac System 8.6<OPTION VALUE="Mac System 9.x">Mac System

9.x<OPTION VALUE="MacOS X">MacOS X<OPTION VALUE="Linux">Linux<OPTION VALUE="BSDI">BSDI<OPTION VALUE="FreeBSD">FreeBSD<OPTION

VALUE="NetBSD">NetBSD<OPTION VALUE="OpenBSD">OpenBSD<OPTION VALUE="AIX">AIX<OPTION VALUE="BeOS">BeOS<OPTION VALUE="HP-UX">HP-UX<OPTION

VALUE="IRIX">IRIX<OPTION VALUE="Neutrino">Neutrino<OPTION VALUE="OpenVMS">OpenVMS<OPTION VALUE="OS/2">OS/2<OPTION VALUE="OSF/1">OSF/1<OPTION

VALUE="Solaris">Solaris<OPTION VALUE="SunOS">SunOS<OPTION VALUE="other">other</SELECT>

​

</td>

​

<td align=left valign=top>

​

<SELECT NAME="priority" MULTIPLE SIZE=7>

​

<OPTION VALUE="--">--<OPTION VALUE="P1">P1<OPTION VALUE="P2">P2<OPTION VALUE="P3">P3<OPTION VALUE="P4">P4<OPTION VALUE="P5">P5</SELECT>

​

</td>

​

<td align=left valign=top>

​

<SELECT NAME="bug severity" MULTIPLE SIZE=7>

​

<OPTION VALUE="blocker">blocker<OPTION VALUE="critical">critical<OPTION VALUE="major">major<OPTION VALUE="normal">normal<OPTION

VALUE="minor">minor<OPTION VALUE="trivial">trivial<OPTION VALUE="enhancement">enhancement</SELECT>

​

</tr>

​

</table>

CS 3240

10 of 76

Ok… so your parser crashed on this input

Test hypothesis

  • Or the table alignments?

<td align=left valign=top>

​

<SELECT NAME="op sys" MULTIPLE SIZE=7>

​

<OPTION VALUE="All">All<OPTION VALUE="Windows 3.1">Windows 3.1<OPTION VALUE="Windows 95">Windows 95<OPTION VALUE="Windows 98">Windows 98<OPTION

VALUE="Windows ME">Windows ME<OPTION VALUE="Windows 2000">Windows 2000<OPTION VALUE="Windows NT">Windows NT<OPTION VALUE="Mac System 7">Mac

System 7<OPTION VALUE="Mac System 7.5">Mac System 7.5<OPTION VALUE="Mac System 7.6.1">Mac System 7.6.1<OPTION VALUE="Mac System 8.0">Mac System

8.0<OPTION VALUE="Mac System 8.5">Mac System 8.5<OPTION VALUE="Mac System 8.6">Mac System 8.6<OPTION VALUE="Mac System 9.x">Mac System

9.x<OPTION VALUE="MacOS X">MacOS X<OPTION VALUE="Linux">Linux<OPTION VALUE="BSDI">BSDI<OPTION VALUE="FreeBSD">FreeBSD<OPTION

VALUE="NetBSD">NetBSD<OPTION VALUE="OpenBSD">OpenBSD<OPTION VALUE="AIX">AIX<OPTION VALUE="BeOS">BeOS<OPTION VALUE="HP-UX">HP-UX<OPTION

VALUE="IRIX">IRIX<OPTION VALUE="Neutrino">Neutrino<OPTION VALUE="OpenVMS">OpenVMS<OPTION VALUE="OS/2">OS/2<OPTION VALUE="OSF/1">OSF/1<OPTION

VALUE="Solaris">Solaris<OPTION VALUE="SunOS">SunOS<OPTION VALUE="other">other</SELECT>

​

</td>

​

<td align=left valign=top>

​

<SELECT NAME="priority" MULTIPLE SIZE=7>

​

<OPTION VALUE="--">--<OPTION VALUE="P1">P1<OPTION VALUE="P2">P2<OPTION VALUE="P3">P3<OPTION VALUE="P4">P4<OPTION VALUE="P5">P5</SELECT>

​

</td>

​

<td align=left valign=top>

​

<SELECT NAME="bug severity" MULTIPLE SIZE=7>

​

<OPTION VALUE="blocker">blocker<OPTION VALUE="critical">critical<OPTION VALUE="major">major<OPTION VALUE="normal">normal<OPTION

VALUE="minor">minor<OPTION VALUE="trivial">trivial<OPTION VALUE="enhancement">enhancement</SELECT>

​

</tr>

​

</table>

<td align=left valign=top>

​

<SELECT NAME="op sys" MULTIPLE SIZE=7>

​

<OPTION VALUE="All">All<OPTION VALUE="Windows 3.1">Windows 3.1<OPTION VALUE="Windows 95">Windows 95<OPTION VALUE="Windows 98">Windows 98<OPTION

VALUE="Windows ME">Windows ME<OPTION VALUE="Windows 2000">Windows 2000<OPTION VALUE="Windows NT">Windows NT<OPTION VALUE="Mac System 7">Mac

System 7<OPTION VALUE="Mac System 7.5">Mac System 7.5<OPTION VALUE="Mac System 7.6.1">Mac System 7.6.1<OPTION VALUE="Mac System 8.0">Mac System

8.0<OPTION VALUE="Mac System 8.5">Mac System 8.5<OPTION VALUE="Mac System 8.6">Mac System 8.6<OPTION VALUE="Mac System 9.x">Mac System

9.x<OPTION VALUE="MacOS X">MacOS X<OPTION VALUE="Linux">Linux<OPTION VALUE="BSDI">BSDI<OPTION VALUE="FreeBSD">FreeBSD<OPTION

VALUE="NetBSD">NetBSD<OPTION VALUE="OpenBSD">OpenBSD<OPTION VALUE="AIX">AIX<OPTION VALUE="BeOS">BeOS<OPTION VALUE="HP-UX">HP-UX<OPTION

VALUE="IRIX">IRIX<OPTION VALUE="Neutrino">Neutrino<OPTION VALUE="OpenVMS">OpenVMS<OPTION VALUE="OS/2">OS/2<OPTION VALUE="OSF/1">OSF/1<OPTION

VALUE="Solaris">Solaris<OPTION VALUE="SunOS">SunOS<OPTION VALUE="other">other</SELECT>

​

</td>

​

<td align=left valign=top>

​

<SELECT NAME="priority" MULTIPLE SIZE=7>

​

<OPTION VALUE="--">--<OPTION VALUE="P1">P1<OPTION VALUE="P2">P2<OPTION VALUE="P3">P3<OPTION VALUE="P4">P4<OPTION VALUE="P5">P5</SELECT>

​

</td>

​

<td align=left valign=top>

​

<SELECT NAME="bug severity" MULTIPLE SIZE=7>

​

<OPTION VALUE="blocker">blocker<OPTION VALUE="critical">critical<OPTION VALUE="major">major<OPTION VALUE="normal">normal<OPTION

VALUE="minor">minor<OPTION VALUE="trivial">trivial<OPTION VALUE="enhancement">enhancement</SELECT>

​

</tr>

​

</table>

CS 3240

11 of 76

Ok… so your parser crashed on this input

Test hypothesis

  • Or the table alignments?

<td align=left valign=top>

​

<SELECT NAME="op sys" MULTIPLE SIZE=7>

​

<OPTION VALUE="All">All<OPTION VALUE="Windows 3.1">Windows 3.1<OPTION VALUE="Windows 95">Windows 95<OPTION VALUE="Windows 98">Windows 98<OPTION

VALUE="Windows ME">Windows ME<OPTION VALUE="Windows 2000">Windows 2000<OPTION VALUE="Windows NT">Windows NT<OPTION VALUE="Mac System 7">Mac

System 7<OPTION VALUE="Mac System 7.5">Mac System 7.5<OPTION VALUE="Mac System 7.6.1">Mac System 7.6.1<OPTION VALUE="Mac System 8.0">Mac System

8.0<OPTION VALUE="Mac System 8.5">Mac System 8.5<OPTION VALUE="Mac System 8.6">Mac System 8.6<OPTION VALUE="Mac System 9.x">Mac System

9.x<OPTION VALUE="MacOS X">MacOS X<OPTION VALUE="Linux">Linux<OPTION VALUE="BSDI">BSDI<OPTION VALUE="FreeBSD">FreeBSD<OPTION

VALUE="NetBSD">NetBSD<OPTION VALUE="OpenBSD">OpenBSD<OPTION VALUE="AIX">AIX<OPTION VALUE="BeOS">BeOS<OPTION VALUE="HP-UX">HP-UX<OPTION

VALUE="IRIX">IRIX<OPTION VALUE="Neutrino">Neutrino<OPTION VALUE="OpenVMS">OpenVMS<OPTION VALUE="OS/2">OS/2<OPTION VALUE="OSF/1">OSF/1<OPTION

VALUE="Solaris">Solaris<OPTION VALUE="SunOS">SunOS<OPTION VALUE="other">other</SELECT>

​

</td>

​

<td align=left valign=top>

​

<SELECT NAME="priority" MULTIPLE SIZE=7>

​

<OPTION VALUE="--">--<OPTION VALUE="P1">P1<OPTION VALUE="P2">P2<OPTION VALUE="P3">P3<OPTION VALUE="P4">P4<OPTION VALUE="P5">P5</SELECT>

​

</td>

​

<td align=left valign=top>

​

<SELECT NAME="bug severity" MULTIPLE SIZE=7>

​

<OPTION VALUE="blocker">blocker<OPTION VALUE="critical">critical<OPTION VALUE="major">major<OPTION VALUE="normal">normal<OPTION

VALUE="minor">minor<OPTION VALUE="trivial">trivial<OPTION VALUE="enhancement">enhancement</SELECT>

​

</tr>

​

</table>

<td align=left valign=top>

​

<SELECT NAME="op sys" MULTIPLE SIZE=7>

​

<OPTION VALUE="All">All<OPTION VALUE="Windows 3.1">Windows 3.1<OPTION VALUE="Windows 95">Windows 95<OPTION VALUE="Windows 98">Windows 98<OPTION

VALUE="Windows ME">Windows ME<OPTION VALUE="Windows 2000">Windows 2000<OPTION VALUE="Windows NT">Windows NT<OPTION VALUE="Mac System 7">Mac

System 7<OPTION VALUE="Mac System 7.5">Mac System 7.5<OPTION VALUE="Mac System 7.6.1">Mac System 7.6.1<OPTION VALUE="Mac System 8.0">Mac System

8.0<OPTION VALUE="Mac System 8.5">Mac System 8.5<OPTION VALUE="Mac System 8.6">Mac System 8.6<OPTION VALUE="Mac System 9.x">Mac System

9.x<OPTION VALUE="MacOS X">MacOS X<OPTION VALUE="Linux">Linux<OPTION VALUE="BSDI">BSDI<OPTION VALUE="FreeBSD">FreeBSD<OPTION

VALUE="NetBSD">NetBSD<OPTION VALUE="OpenBSD">OpenBSD<OPTION VALUE="AIX">AIX<OPTION VALUE="BeOS">BeOS<OPTION VALUE="HP-UX">HP-UX<OPTION

VALUE="IRIX">IRIX<OPTION VALUE="Neutrino">Neutrino<OPTION VALUE="OpenVMS">OpenVMS<OPTION VALUE="OS/2">OS/2<OPTION VALUE="OSF/1">OSF/1<OPTION

VALUE="Solaris">Solaris<OPTION VALUE="SunOS">SunOS<OPTION VALUE="other">other</SELECT>

​

</td>

​

<td align=left valign=top>

​

<SELECT NAME="priority" MULTIPLE SIZE=7>

​

<OPTION VALUE="--">--<OPTION VALUE="P1">P1<OPTION VALUE="P2">P2<OPTION VALUE="P3">P3<OPTION VALUE="P4">P4<OPTION VALUE="P5">P5</SELECT>

​

</td>

​

<td align=left valign=top>

​

<SELECT NAME="bug severity" MULTIPLE SIZE=7>

​

<OPTION VALUE="blocker">blocker<OPTION VALUE="critical">critical<OPTION VALUE="major">major<OPTION VALUE="normal">normal<OPTION

VALUE="minor">minor<OPTION VALUE="trivial">trivial<OPTION VALUE="enhancement">enhancement</SELECT>

​

</tr>

​

</table>

<td align=left valign=top>

​

<SELECT NAME="op sys" MULTIPLE SIZE=7>

​

<OPTION VALUE="All">All<OPTION VALUE="Windows 3.1">Windows 3.1<OPTION VALUE="Windows 95">Windows 95<OPTION VALUE="Windows 98">Windows 98<OPTION

VALUE="Windows ME">Windows ME<OPTION VALUE="Windows 2000">Windows 2000<OPTION VALUE="Windows NT">Windows NT<OPTION VALUE="Mac System 7">Mac

System 7<OPTION VALUE="Mac System 7.5">Mac System 7.5<OPTION VALUE="Mac System 7.6.1">Mac System 7.6.1<OPTION VALUE="Mac System 8.0">Mac System

8.0<OPTION VALUE="Mac System 8.5">Mac System 8.5<OPTION VALUE="Mac System 8.6">Mac System 8.6<OPTION VALUE="Mac System 9.x">Mac System

9.x<OPTION VALUE="MacOS X">MacOS X<OPTION VALUE="Linux">Linux<OPTION VALUE="BSDI">BSDI<OPTION VALUE="FreeBSD">FreeBSD<OPTION

VALUE="NetBSD">NetBSD<OPTION VALUE="OpenBSD">OpenBSD<OPTION VALUE="AIX">AIX<OPTION VALUE="BeOS">BeOS<OPTION VALUE="HP-UX">HP-UX<OPTION

VALUE="IRIX">IRIX<OPTION VALUE="Neutrino">Neutrino<OPTION VALUE="OpenVMS">OpenVMS<OPTION VALUE="OS/2">OS/2<OPTION VALUE="OSF/1">OSF/1<OPTION

VALUE="Solaris">Solaris<OPTION VALUE="SunOS">SunOS<OPTION VALUE="other">other</SELECT>

​

</td>

​

<td align=left valign=top>

​

<SELECT NAME="priority" MULTIPLE SIZE=7>

​

<OPTION VALUE="--">--<OPTION VALUE="P1">P1<OPTION VALUE="P2">P2<OPTION VALUE="P3">P3<OPTION VALUE="P4">P4<OPTION VALUE="P5">P5</SELECT>

​

</td>

​

<td align=left valign=top>

​

<SELECT NAME="bug severity" MULTIPLE SIZE=7>

​

<OPTION VALUE="blocker">blocker<OPTION VALUE="critical">critical<OPTION VALUE="major">major<OPTION VALUE="normal">normal<OPTION

VALUE="minor">minor<OPTION VALUE="trivial">trivial<OPTION VALUE="enhancement">enhancement</SELECT>

​

</tr>

​

</table>

CS 3240

12 of 76

Ok… so your parser crashed on this input

Test hypothesis

  • Or the table alignments? Ok, is not this

<td align=left valign=top>

​

<SELECT NAME="op sys" MULTIPLE SIZE=7>

​

<OPTION VALUE="All">All<OPTION VALUE="Windows 3.1">Windows 3.1<OPTION VALUE="Windows 95">Windows 95<OPTION VALUE="Windows 98">Windows 98<OPTION

VALUE="Windows ME">Windows ME<OPTION VALUE="Windows 2000">Windows 2000<OPTION VALUE="Windows NT">Windows NT<OPTION VALUE="Mac System 7">Mac

System 7<OPTION VALUE="Mac System 7.5">Mac System 7.5<OPTION VALUE="Mac System 7.6.1">Mac System 7.6.1<OPTION VALUE="Mac System 8.0">Mac System

8.0<OPTION VALUE="Mac System 8.5">Mac System 8.5<OPTION VALUE="Mac System 8.6">Mac System 8.6<OPTION VALUE="Mac System 9.x">Mac System

9.x<OPTION VALUE="MacOS X">MacOS X<OPTION VALUE="Linux">Linux<OPTION VALUE="BSDI">BSDI<OPTION VALUE="FreeBSD">FreeBSD<OPTION

VALUE="NetBSD">NetBSD<OPTION VALUE="OpenBSD">OpenBSD<OPTION VALUE="AIX">AIX<OPTION VALUE="BeOS">BeOS<OPTION VALUE="HP-UX">HP-UX<OPTION

VALUE="IRIX">IRIX<OPTION VALUE="Neutrino">Neutrino<OPTION VALUE="OpenVMS">OpenVMS<OPTION VALUE="OS/2">OS/2<OPTION VALUE="OSF/1">OSF/1<OPTION

VALUE="Solaris">Solaris<OPTION VALUE="SunOS">SunOS<OPTION VALUE="other">other</SELECT>

​

</td>

​

<td align=left valign=top>

​

<SELECT NAME="priority" MULTIPLE SIZE=7>

​

<OPTION VALUE="--">--<OPTION VALUE="P1">P1<OPTION VALUE="P2">P2<OPTION VALUE="P3">P3<OPTION VALUE="P4">P4<OPTION VALUE="P5">P5</SELECT>

​

</td>

​

<td align=left valign=top>

​

<SELECT NAME="bug severity" MULTIPLE SIZE=7>

​

<OPTION VALUE="blocker">blocker<OPTION VALUE="critical">critical<OPTION VALUE="major">major<OPTION VALUE="normal">normal<OPTION

VALUE="minor">minor<OPTION VALUE="trivial">trivial<OPTION VALUE="enhancement">enhancement</SELECT>

​

</tr>

​

</table>

<td align=left valign=top>

​

<SELECT NAME="op sys" MULTIPLE SIZE=7>

​

<OPTION VALUE="All">All<OPTION VALUE="Windows 3.1">Windows 3.1<OPTION VALUE="Windows 95">Windows 95<OPTION VALUE="Windows 98">Windows 98<OPTION

VALUE="Windows ME">Windows ME<OPTION VALUE="Windows 2000">Windows 2000<OPTION VALUE="Windows NT">Windows NT<OPTION VALUE="Mac System 7">Mac

System 7<OPTION VALUE="Mac System 7.5">Mac System 7.5<OPTION VALUE="Mac System 7.6.1">Mac System 7.6.1<OPTION VALUE="Mac System 8.0">Mac System

8.0<OPTION VALUE="Mac System 8.5">Mac System 8.5<OPTION VALUE="Mac System 8.6">Mac System 8.6<OPTION VALUE="Mac System 9.x">Mac System

9.x<OPTION VALUE="MacOS X">MacOS X<OPTION VALUE="Linux">Linux<OPTION VALUE="BSDI">BSDI<OPTION VALUE="FreeBSD">FreeBSD<OPTION

VALUE="NetBSD">NetBSD<OPTION VALUE="OpenBSD">OpenBSD<OPTION VALUE="AIX">AIX<OPTION VALUE="BeOS">BeOS<OPTION VALUE="HP-UX">HP-UX<OPTION

VALUE="IRIX">IRIX<OPTION VALUE="Neutrino">Neutrino<OPTION VALUE="OpenVMS">OpenVMS<OPTION VALUE="OS/2">OS/2<OPTION VALUE="OSF/1">OSF/1<OPTION

VALUE="Solaris">Solaris<OPTION VALUE="SunOS">SunOS<OPTION VALUE="other">other</SELECT>

​

</td>

​

<td align=left valign=top>

​

<SELECT NAME="priority" MULTIPLE SIZE=7>

​

<OPTION VALUE="--">--<OPTION VALUE="P1">P1<OPTION VALUE="P2">P2<OPTION VALUE="P3">P3<OPTION VALUE="P4">P4<OPTION VALUE="P5">P5</SELECT>

​

</td>

​

<td align=left valign=top>

​

<SELECT NAME="bug severity" MULTIPLE SIZE=7>

​

<OPTION VALUE="blocker">blocker<OPTION VALUE="critical">critical<OPTION VALUE="major">major<OPTION VALUE="normal">normal<OPTION

VALUE="minor">minor<OPTION VALUE="trivial">trivial<OPTION VALUE="enhancement">enhancement</SELECT>

​

</tr>

​

</table>

<td align=left valign=top>

​

<SELECT NAME="op sys" MULTIPLE SIZE=7>

​

<OPTION VALUE="All">All<OPTION VALUE="Windows 3.1">Windows 3.1<OPTION VALUE="Windows 95">Windows 95<OPTION VALUE="Windows 98">Windows 98<OPTION

VALUE="Windows ME">Windows ME<OPTION VALUE="Windows 2000">Windows 2000<OPTION VALUE="Windows NT">Windows NT<OPTION VALUE="Mac System 7">Mac

System 7<OPTION VALUE="Mac System 7.5">Mac System 7.5<OPTION VALUE="Mac System 7.6.1">Mac System 7.6.1<OPTION VALUE="Mac System 8.0">Mac System

8.0<OPTION VALUE="Mac System 8.5">Mac System 8.5<OPTION VALUE="Mac System 8.6">Mac System 8.6<OPTION VALUE="Mac System 9.x">Mac System

9.x<OPTION VALUE="MacOS X">MacOS X<OPTION VALUE="Linux">Linux<OPTION VALUE="BSDI">BSDI<OPTION VALUE="FreeBSD">FreeBSD<OPTION

VALUE="NetBSD">NetBSD<OPTION VALUE="OpenBSD">OpenBSD<OPTION VALUE="AIX">AIX<OPTION VALUE="BeOS">BeOS<OPTION VALUE="HP-UX">HP-UX<OPTION

VALUE="IRIX">IRIX<OPTION VALUE="Neutrino">Neutrino<OPTION VALUE="OpenVMS">OpenVMS<OPTION VALUE="OS/2">OS/2<OPTION VALUE="OSF/1">OSF/1<OPTION

VALUE="Solaris">Solaris<OPTION VALUE="SunOS">SunOS<OPTION VALUE="other">other</SELECT>

​

</td>

​

<td align=left valign=top>

​

<SELECT NAME="priority" MULTIPLE SIZE=7>

​

<OPTION VALUE="--">--<OPTION VALUE="P1">P1<OPTION VALUE="P2">P2<OPTION VALUE="P3">P3<OPTION VALUE="P4">P4<OPTION VALUE="P5">P5</SELECT>

​

</td>

​

<td align=left valign=top>

​

<SELECT NAME="bug severity" MULTIPLE SIZE=7>

​

<OPTION VALUE="blocker">blocker<OPTION VALUE="critical">critical<OPTION VALUE="major">major<OPTION VALUE="normal">normal<OPTION

VALUE="minor">minor<OPTION VALUE="trivial">trivial<OPTION VALUE="enhancement">enhancement</SELECT>

​

</tr>

​

</table>

<td align=left valign=top>

​

<SELECT NAME="op sys" MULTIPLE SIZE=7>

​

<OPTION VALUE="All">All<OPTION VALUE="Windows 3.1">Windows 3.1<OPTION VALUE="Windows 95">Windows 95<OPTION VALUE="Windows 98">Windows 98<OPTION

VALUE="Windows ME">Windows ME<OPTION VALUE="Windows 2000">Windows 2000<OPTION VALUE="Windows NT">Windows NT<OPTION VALUE="Mac System 7">Mac

System 7<OPTION VALUE="Mac System 7.5">Mac System 7.5<OPTION VALUE="Mac System 7.6.1">Mac System 7.6.1<OPTION VALUE="Mac System 8.0">Mac System

8.0<OPTION VALUE="Mac System 8.5">Mac System 8.5<OPTION VALUE="Mac System 8.6">Mac System 8.6<OPTION VALUE="Mac System 9.x">Mac System

9.x<OPTION VALUE="MacOS X">MacOS X<OPTION VALUE="Linux">Linux<OPTION VALUE="BSDI">BSDI<OPTION VALUE="FreeBSD">FreeBSD<OPTION

VALUE="NetBSD">NetBSD<OPTION VALUE="OpenBSD">OpenBSD<OPTION VALUE="AIX">AIX<OPTION VALUE="BeOS">BeOS<OPTION VALUE="HP-UX">HP-UX<OPTION

VALUE="IRIX">IRIX<OPTION VALUE="Neutrino">Neutrino<OPTION VALUE="OpenVMS">OpenVMS<OPTION VALUE="OS/2">OS/2<OPTION VALUE="OSF/1">OSF/1<OPTION

VALUE="Solaris">Solaris<OPTION VALUE="SunOS">SunOS<OPTION VALUE="other">other</SELECT>

​

</td>

​

<td align=left valign=top>

​

<SELECT NAME="priority" MULTIPLE SIZE=7>

​

<OPTION VALUE="--">--<OPTION VALUE="P1">P1<OPTION VALUE="P2">P2<OPTION VALUE="P3">P3<OPTION VALUE="P4">P4<OPTION VALUE="P5">P5</SELECT>

​

</td>

​

<td align=left valign=top>

​

<SELECT NAME="bug severity" MULTIPLE SIZE=7>

​

<OPTION VALUE="blocker">blocker<OPTION VALUE="critical">critical<OPTION VALUE="major">major<OPTION VALUE="normal">normal<OPTION

VALUE="minor">minor<OPTION VALUE="trivial">trivial<OPTION VALUE="enhancement">enhancement</SELECT>

​

</tr>

​

</table>

CS 3240

13 of 76

Ok… so your parser crashed on this input

Test hypothesis

  • Or the table alignments?

Test hypothesis

  • Or the table alignments? Ok, is not this

<td align=left valign=top>

​

<SELECT NAME="op sys" MULTIPLE SIZE=7>

​

<OPTION VALUE="All">All<OPTION VALUE="Windows 3.1">Windows 3.1<OPTION VALUE="Windows 95">Windows 95<OPTION VALUE="Windows 98">Windows 98<OPTION

VALUE="Windows ME">Windows ME<OPTION VALUE="Windows 2000">Windows 2000<OPTION VALUE="Windows NT">Windows NT<OPTION VALUE="Mac System 7">Mac

System 7<OPTION VALUE="Mac System 7.5">Mac System 7.5<OPTION VALUE="Mac System 7.6.1">Mac System 7.6.1<OPTION VALUE="Mac System 8.0">Mac System

8.0<OPTION VALUE="Mac System 8.5">Mac System 8.5<OPTION VALUE="Mac System 8.6">Mac System 8.6<OPTION VALUE="Mac System 9.x">Mac System

9.x<OPTION VALUE="MacOS X">MacOS X<OPTION VALUE="Linux">Linux<OPTION VALUE="BSDI">BSDI<OPTION VALUE="FreeBSD">FreeBSD<OPTION

VALUE="NetBSD">NetBSD<OPTION VALUE="OpenBSD">OpenBSD<OPTION VALUE="AIX">AIX<OPTION VALUE="BeOS">BeOS<OPTION VALUE="HP-UX">HP-UX<OPTION

VALUE="IRIX">IRIX<OPTION VALUE="Neutrino">Neutrino<OPTION VALUE="OpenVMS">OpenVMS<OPTION VALUE="OS/2">OS/2<OPTION VALUE="OSF/1">OSF/1<OPTION

VALUE="Solaris">Solaris<OPTION VALUE="SunOS">SunOS<OPTION VALUE="other">other</SELECT>

​

</td>

​

<td align=left valign=top>

​

<SELECT NAME="priority" MULTIPLE SIZE=7>

​

<OPTION VALUE="--">--<OPTION VALUE="P1">P1<OPTION VALUE="P2">P2<OPTION VALUE="P3">P3<OPTION VALUE="P4">P4<OPTION VALUE="P5">P5</SELECT>

​

</td>

​

<td align=left valign=top>

​

<SELECT NAME="bug severity" MULTIPLE SIZE=7>

​

<OPTION VALUE="blocker">blocker<OPTION VALUE="critical">critical<OPTION VALUE="major">major<OPTION VALUE="normal">normal<OPTION

VALUE="minor">minor<OPTION VALUE="trivial">trivial<OPTION VALUE="enhancement">enhancement</SELECT>

​

</tr>

​

</table>

<td align=left valign=top>

​

<SELECT NAME="op sys" MULTIPLE SIZE=7>

​

<OPTION VALUE="All">All<OPTION VALUE="Windows 3.1">Windows 3.1<OPTION VALUE="Windows 95">Windows 95<OPTION VALUE="Windows 98">Windows 98<OPTION

VALUE="Windows ME">Windows ME<OPTION VALUE="Windows 2000">Windows 2000<OPTION VALUE="Windows NT">Windows NT<OPTION VALUE="Mac System 7">Mac

System 7<OPTION VALUE="Mac System 7.5">Mac System 7.5<OPTION VALUE="Mac System 7.6.1">Mac System 7.6.1<OPTION VALUE="Mac System 8.0">Mac System

8.0<OPTION VALUE="Mac System 8.5">Mac System 8.5<OPTION VALUE="Mac System 8.6">Mac System 8.6<OPTION VALUE="Mac System 9.x">Mac System

9.x<OPTION VALUE="MacOS X">MacOS X<OPTION VALUE="Linux">Linux<OPTION VALUE="BSDI">BSDI<OPTION VALUE="FreeBSD">FreeBSD<OPTION

VALUE="NetBSD">NetBSD<OPTION VALUE="OpenBSD">OpenBSD<OPTION VALUE="AIX">AIX<OPTION VALUE="BeOS">BeOS<OPTION VALUE="HP-UX">HP-UX<OPTION

VALUE="IRIX">IRIX<OPTION VALUE="Neutrino">Neutrino<OPTION VALUE="OpenVMS">OpenVMS<OPTION VALUE="OS/2">OS/2<OPTION VALUE="OSF/1">OSF/1<OPTION

VALUE="Solaris">Solaris<OPTION VALUE="SunOS">SunOS<OPTION VALUE="other">other</SELECT>

​

</td>

​

<td align=left valign=top>

​

<SELECT NAME="priority" MULTIPLE SIZE=7>

​

<OPTION VALUE="--">--<OPTION VALUE="P1">P1<OPTION VALUE="P2">P2<OPTION VALUE="P3">P3<OPTION VALUE="P4">P4<OPTION VALUE="P5">P5</SELECT>

​

</td>

​

<td align=left valign=top>

​

<SELECT NAME="bug severity" MULTIPLE SIZE=7>

​

<OPTION VALUE="blocker">blocker<OPTION VALUE="critical">critical<OPTION VALUE="major">major<OPTION VALUE="normal">normal<OPTION

VALUE="minor">minor<OPTION VALUE="trivial">trivial<OPTION VALUE="enhancement">enhancement</SELECT>

​

</tr>

​

</table>

<td align=left valign=top>

​

<SELECT NAME="op sys" MULTIPLE SIZE=7>

​

<OPTION VALUE="All">All<OPTION VALUE="Windows 3.1">Windows 3.1<OPTION VALUE="Windows 95">Windows 95<OPTION VALUE="Windows 98">Windows 98<OPTION

VALUE="Windows ME">Windows ME<OPTION VALUE="Windows 2000">Windows 2000<OPTION VALUE="Windows NT">Windows NT<OPTION VALUE="Mac System 7">Mac

System 7<OPTION VALUE="Mac System 7.5">Mac System 7.5<OPTION VALUE="Mac System 7.6.1">Mac System 7.6.1<OPTION VALUE="Mac System 8.0">Mac System

8.0<OPTION VALUE="Mac System 8.5">Mac System 8.5<OPTION VALUE="Mac System 8.6">Mac System 8.6<OPTION VALUE="Mac System 9.x">Mac System

9.x<OPTION VALUE="MacOS X">MacOS X<OPTION VALUE="Linux">Linux<OPTION VALUE="BSDI">BSDI<OPTION VALUE="FreeBSD">FreeBSD<OPTION

VALUE="NetBSD">NetBSD<OPTION VALUE="OpenBSD">OpenBSD<OPTION VALUE="AIX">AIX<OPTION VALUE="BeOS">BeOS<OPTION VALUE="HP-UX">HP-UX<OPTION

VALUE="IRIX">IRIX<OPTION VALUE="Neutrino">Neutrino<OPTION VALUE="OpenVMS">OpenVMS<OPTION VALUE="OS/2">OS/2<OPTION VALUE="OSF/1">OSF/1<OPTION

VALUE="Solaris">Solaris<OPTION VALUE="SunOS">SunOS<OPTION VALUE="other">other</SELECT>

​

</td>

​

<td align=left valign=top>

​

<SELECT NAME="priority" MULTIPLE SIZE=7>

​

<OPTION VALUE="--">--<OPTION VALUE="P1">P1<OPTION VALUE="P2">P2<OPTION VALUE="P3">P3<OPTION VALUE="P4">P4<OPTION VALUE="P5">P5</SELECT>

​

</td>

​

<td align=left valign=top>

​

<SELECT NAME="bug severity" MULTIPLE SIZE=7>

​

<OPTION VALUE="blocker">blocker<OPTION VALUE="critical">critical<OPTION VALUE="major">major<OPTION VALUE="normal">normal<OPTION

VALUE="minor">minor<OPTION VALUE="trivial">trivial<OPTION VALUE="enhancement">enhancement</SELECT>

​

</tr>

​

</table>

<td align=left valign=top>

​

<SELECT NAME="op sys" MULTIPLE SIZE=7>

​

<OPTION VALUE="All">All<OPTION VALUE="Windows 3.1">Windows 3.1<OPTION VALUE="Windows 95">Windows 95<OPTION VALUE="Windows 98">Windows 98<OPTION

VALUE="Windows ME">Windows ME<OPTION VALUE="Windows 2000">Windows 2000<OPTION VALUE="Windows NT">Windows NT<OPTION VALUE="Mac System 7">Mac

System 7<OPTION VALUE="Mac System 7.5">Mac System 7.5<OPTION VALUE="Mac System 7.6.1">Mac System 7.6.1<OPTION VALUE="Mac System 8.0">Mac System

8.0<OPTION VALUE="Mac System 8.5">Mac System 8.5<OPTION VALUE="Mac System 8.6">Mac System 8.6<OPTION VALUE="Mac System 9.x">Mac System

9.x<OPTION VALUE="MacOS X">MacOS X<OPTION VALUE="Linux">Linux<OPTION VALUE="BSDI">BSDI<OPTION VALUE="FreeBSD">FreeBSD<OPTION

VALUE="NetBSD">NetBSD<OPTION VALUE="OpenBSD">OpenBSD<OPTION VALUE="AIX">AIX<OPTION VALUE="BeOS">BeOS<OPTION VALUE="HP-UX">HP-UX<OPTION

VALUE="IRIX">IRIX<OPTION VALUE="Neutrino">Neutrino<OPTION VALUE="OpenVMS">OpenVMS<OPTION VALUE="OS/2">OS/2<OPTION VALUE="OSF/1">OSF/1<OPTION

VALUE="Solaris">Solaris<OPTION VALUE="SunOS">SunOS<OPTION VALUE="other">other</SELECT>

​

</td>

​

<td align=left valign=top>

​

<SELECT NAME="priority" MULTIPLE SIZE=7>

​

<OPTION VALUE="--">--<OPTION VALUE="P1">P1<OPTION VALUE="P2">P2<OPTION VALUE="P3">P3<OPTION VALUE="P4">P4<OPTION VALUE="P5">P5</SELECT>

​

</td>

​

<td align=left valign=top>

​

<SELECT NAME="bug severity" MULTIPLE SIZE=7>

​

<OPTION VALUE="blocker">blocker<OPTION VALUE="critical">critical<OPTION VALUE="major">major<OPTION VALUE="normal">normal<OPTION

VALUE="minor">minor<OPTION VALUE="trivial">trivial<OPTION VALUE="enhancement">enhancement</SELECT>

​

</tr>

​

</table>

<td align=left valign=top>

​

<SELECT NAME="op sys" MULTIPLE SIZE=7>

​

<OPTION VALUE="All">All<OPTION VALUE="Windows 3.1">Windows 3.1<OPTION VALUE="Windows 95">Windows 95<OPTION VALUE="Windows 98">Windows 98<OPTION

VALUE="Windows ME">Windows ME<OPTION VALUE="Windows 2000">Windows 2000<OPTION VALUE="Windows NT">Windows NT<OPTION VALUE="Mac System 7">Mac

System 7<OPTION VALUE="Mac System 7.5">Mac System 7.5<OPTION VALUE="Mac System 7.6.1">Mac System 7.6.1<OPTION VALUE="Mac System 8.0">Mac System

8.0<OPTION VALUE="Mac System 8.5">Mac System 8.5<OPTION VALUE="Mac System 8.6">Mac System 8.6<OPTION VALUE="Mac System 9.x">Mac System

9.x<OPTION VALUE="MacOS X">MacOS X<OPTION VALUE="Linux">Linux<OPTION VALUE="BSDI">BSDI<OPTION VALUE="FreeBSD">FreeBSD<OPTION

VALUE="NetBSD">NetBSD<OPTION VALUE="OpenBSD">OpenBSD<OPTION VALUE="AIX">AIX<OPTION VALUE="BeOS">BeOS<OPTION VALUE="HP-UX">HP-UX<OPTION

VALUE="IRIX">IRIX<OPTION VALUE="Neutrino">Neutrino<OPTION VALUE="OpenVMS">OpenVMS<OPTION VALUE="OS/2">OS/2<OPTION VALUE="OSF/1">OSF/1<OPTION

VALUE="Solaris">Solaris<OPTION VALUE="SunOS">SunOS<OPTION VALUE="other">other</SELECT>

​

</td>

​

<td align=left valign=top>

​

<SELECT NAME="priority" MULTIPLE SIZE=7>

​

<OPTION VALUE="--">--<OPTION VALUE="P1">P1<OPTION VALUE="P2">P2<OPTION VALUE="P3">P3<OPTION VALUE="P4">P4<OPTION VALUE="P5">P5</SELECT>

​

</td>

​

<td align=left valign=top>

​

<SELECT NAME="bug severity" MULTIPLE SIZE=7>

​

<OPTION VALUE="blocker">blocker<OPTION VALUE="critical">critical<OPTION VALUE="major">major<OPTION VALUE="normal">normal<OPTION

VALUE="minor">minor<OPTION VALUE="trivial">trivial<OPTION VALUE="enhancement">enhancement</SELECT>

​

</tr>

​

</table>

Process is experimental but not systematic and tedious

CS 3240

14 of 76

Ok… so your parser crashed on this input

<td align=left valign=top>

​

<SELECT NAME="op sys" MULTIPLE SIZE=7>

​

<OPTION VALUE="All">All<OPTION VALUE="Windows 3.1">Windows 3.1<OPTION VALUE="Windows 95">Windows 95<OPTION VALUE="Windows 98">Windows 98<OPTION

VALUE="Windows ME">Windows ME<OPTION VALUE="Windows 2000">Windows 2000<OPTION VALUE="Windows NT">Windows NT<OPTION VALUE="Mac System 7">Mac

System 7<OPTION VALUE="Mac System 7.5">Mac System 7.5<OPTION VALUE="Mac System 7.6.1">Mac System 7.6.1<OPTION VALUE="Mac System 8.0">Mac System

8.0<OPTION VALUE="Mac System 8.5">Mac System 8.5<OPTION VALUE="Mac System 8.6">Mac System 8.6<OPTION VALUE="Mac System 9.x">Mac System

9.x<OPTION VALUE="MacOS X">MacOS X<OPTION VALUE="Linux">Linux<OPTION VALUE="BSDI">BSDI<OPTION VALUE="FreeBSD">FreeBSD<OPTION

VALUE="NetBSD">NetBSD<OPTION VALUE="OpenBSD">OpenBSD<OPTION VALUE="AIX">AIX<OPTION VALUE="BeOS">BeOS<OPTION VALUE="HP-UX">HP-UX<OPTION

VALUE="IRIX">IRIX<OPTION VALUE="Neutrino">Neutrino<OPTION VALUE="OpenVMS">OpenVMS<OPTION VALUE="OS/2">OS/2<OPTION VALUE="OSF/1">OSF/1<OPTION

VALUE="Solaris">Solaris<OPTION VALUE="SunOS">SunOS<OPTION VALUE="other">other</SELECT>

​

</td>

​

<td align=left valign=top>

​

<SELECT NAME="priority" MULTIPLE SIZE=7>

​

<OPTION VALUE="--">--<OPTION VALUE="P1">P1<OPTION VALUE="P2">P2<OPTION VALUE="P3">P3<OPTION VALUE="P4">P4<OPTION VALUE="P5">P5</SELECT>

​

</td>

​

<td align=left valign=top>

​

<SELECT NAME="bug severity" MULTIPLE SIZE=7>

​

<OPTION VALUE="blocker">blocker<OPTION VALUE="critical">critical<OPTION VALUE="major">major<OPTION VALUE="normal">normal<OPTION

VALUE="minor">minor<OPTION VALUE="trivial">trivial<OPTION VALUE="enhancement">enhancement</SELECT>

​

</tr>

​

</table>

Hypothesis Generation

  • Maybe is the load of the 10,000 tokens?
  • Maybe some of the specific OPTIONS?
  • Maybe is the sequence of SELECT and OPTIONS?
  • Maybe is the table? Or the table alignments?
  • Or ...?

https://www.tlnt.com/

CS 3240

15 of 76

Failure simplification / isolation

Program

Test

Refine

Hypotheses

Pass

Fails

?

CS 3240

16 of 76

Failure Simplification

To this

<td align=left valign=top>

​

<SELECT NAME="op sys" MULTIPLE SIZE=7>

​

<OPTION VALUE="All">All<OPTION VALUE="Windows 3.1">Windows 3.1<OPTION VALUE="Windows 95">Windows 95<OPTION VALUE="Windows 98">Windows 98<OPTION

VALUE="Windows ME">Windows ME<OPTION VALUE="Windows 2000">Windows 2000<OPTION VALUE="Windows NT">Windows NT<OPTION VALUE="Mac System 7">Mac

System 7<OPTION VALUE="Mac System 7.5">Mac System 7.5<OPTION VALUE="Mac System 7.6.1">Mac System 7.6.1<OPTION VALUE="Mac System 8.0">Mac System

8.0<OPTION VALUE="Mac System 8.5">Mac System 8.5<OPTION VALUE="Mac System 8.6">Mac System 8.6<OPTION VALUE="Mac System 9.x">Mac System

9.x<OPTION VALUE="MacOS X">MacOS X<OPTION VALUE="Linux">Linux<OPTION VALUE="BSDI">BSDI<OPTION VALUE="FreeBSD">FreeBSD<OPTION

VALUE="NetBSD">NetBSD<OPTION VALUE="OpenBSD">OpenBSD<OPTION VALUE="AIX">AIX<OPTION VALUE="BeOS">BeOS<OPTION VALUE="HP-UX">HP-UX<OPTION

VALUE="IRIX">IRIX<OPTION VALUE="Neutrino">Neutrino<OPTION VALUE="OpenVMS">OpenVMS<OPTION VALUE="OS/2">OS/2<OPTION VALUE="OSF/1">OSF/1<OPTION

VALUE="Solaris">Solaris<OPTION VALUE="SunOS">SunOS<OPTION VALUE="other">other</SELECT>

​

</td>

​

<td align=left valign=top>

​

<SELECT NAME="priority" MULTIPLE SIZE=7>

​

<OPTION VALUE="--">--<OPTION VALUE="P1">P1<OPTION VALUE="P2">P2<OPTION VALUE="P3">P3<OPTION VALUE="P4">P4<OPTION VALUE="P5">P5</SELECT>

​

</td>

​

<td align=left valign=top>

​

<SELECT NAME="bug severity" MULTIPLE SIZE=7>

​

<OPTION VALUE="blocker">blocker<OPTION VALUE="critical">critical<OPTION VALUE="major">major<OPTION VALUE="normal">normal<OPTION

VALUE="minor">minor<OPTION VALUE="trivial">trivial<OPTION VALUE="enhancement">enhancement</SELECT>

​

</tr>

​

</table>

<SELECT>

CS 3240

17 of 76

Failure Simplification: Why

CS 3240

18 of 76

Failure Simplification: Why?

  • Ease debugging
    • Smaller tests have smaller states / shorter execs
  • Ease communication
    • Simpler test case is easier to communicate
  • Identify duplicates
    • Simplified tests subsumes duplicates

​

CS 3240

19 of 76

Approach: iterative search

​

Basics of procedure known as “delta debugging”

​

Repeat until “small-enough” input causes failure

​

  • Throw away portion of input

​

2. If the output is still wrong go back to 1

​

3. Else go back to previous state and discard other portion.

Much more information about DD can be found here: https://www.st.cs.uni-saarland.de/dd/

CS 3240

20 of 76

Approach: iterative binary search

​

CS 3240

21 of 76

Approach: iterative binary search

​

t1

CS 3240

22 of 76

Approach: iterative binary search

​

t1

CS 3240

23 of 76

Approach: iterative binary search

​

t1

t2

CS 3240

24 of 76

Approach: iterative binary search

​

t1

t2

CS 3240

25 of 76

Approach: iterative binary search

​

t1

t2

t3

CS 3240

26 of 76

Approach: iterative binary search

​

t1

t2

t3

t4

CS 3240

27 of 76

Approach: iterative binary search

​

t1

t2

t3

t4

t5

CS 3240

28 of 76

Approach: iterative binary search

​

t1

t2

t3

t4

t5

t6

CS 3240

29 of 76

<td align=left valign=top>

​

<SELECT NAME="op sys" MULTIPLE SIZE=7>

​

<OPTION VALUE="All">All<OPTION VALUE="Windows 3.1">Windows 3.1<OPTION VALUE="Windows 95">Windows 95<OPTION VALUE="Windows 98">Windows 98<OPTION

VALUE="Windows ME">Windows ME<OPTION VALUE="Windows 2000">Windows 2000<OPTION VALUE="Windows NT">Windows NT<OPTION VALUE="Mac System 7">Mac

System 7<OPTION VALUE="Mac System 7.5">Mac System 7.5<OPTION VALUE="Mac System 7.6.1">Mac System 7.6.1<OPTION VALUE="Mac System 8.0">Mac System

8.0<OPTION VALUE="Mac System 8.5">Mac System 8.5<OPTION VALUE="Mac System 8.6">Mac System 8.6<OPTION VALUE="Mac System 9.x">Mac System

9.x<OPTION VALUE="MacOS X">MacOS X<OPTION VALUE="Linux">Linux<OPTION VALUE="BSDI">BSDI<OPTION VALUE="FreeBSD">FreeBSD<OPTION

VALUE="NetBSD">NetBSD<OPTION VALUE="OpenBSD">OpenBSD<OPTION VALUE="AIX">AIX<OPTION VALUE="BeOS">BeOS<OPTION VALUE="HP-UX">HP-UX<OPTION

VALUE="IRIX">IRIX<OPTION VALUE="Neutrino">Neutrino<OPTION VALUE="OpenVMS">OpenVMS<OPTION VALUE="OS/2">OS/2<OPTION VALUE="OSF/1">OSF/1<OPTION

VALUE="Solaris">Solaris<OPTION VALUE="SunOS">SunOS<OPTION VALUE="other">other</SELECT>

​

</td>

​

<td align=left valign=top>

​

<SELECT NAME="priority" MULTIPLE SIZE=7>

​

<OPTION VALUE="--">--<OPTION VALUE="P1">P1<OPTION VALUE="P2">P2<OPTION VALUE="P3">P3<OPTION VALUE="P4">P4<OPTION VALUE="P5">P5</SELECT>

​

</td>

​

<td align=left valign=top>

​

<SELECT NAME="bug severity" MULTIPLE SIZE=7>

​

<OPTION VALUE="blocker">blocker<OPTION VALUE="critical">critical<OPTION VALUE="major">major<OPTION VALUE="normal">normal<OPTION

VALUE="minor">minor<OPTION VALUE="trivial">trivial<OPTION VALUE="enhancement">enhancement</SELECT>

​

</tr>

​

</table>

CS 3240

30 of 76

<td align=left valign=top>

​

<SELECT NAME="op sys" MULTIPLE SIZE=7>

​

<OPTION VALUE="All">All<OPTION VALUE="Windows 3.1">Windows 3.1<OPTION VALUE="Windows 95">Windows 95<OPTION VALUE="Windows 98">Windows 98<OPTION

VALUE="Windows ME">Windows ME<OPTION VALUE="Windows 2000">Windows 2000<OPTION VALUE="Windows NT">Windows NT<OPTION VALUE="Mac System 7">Mac

System 7<OPTION VALUE="Mac System 7.5">Mac System 7.5<OPTION VALUE="Mac System 7.6.1">Mac System 7.6.1<OPTION VALUE="Mac System 8.0">Mac System

8.0<OPTION VALUE="Mac System 8.5">Mac System 8.5<OPTION VALUE="Mac System 8.6">Mac System 8.6<OPTION VALUE="Mac System 9.x">Mac System

9.x<OPTION VALUE="MacOS X">MacOS X<OPTION VALUE="Linux">Linux<OPTION VALUE="BSDI">BSDI<OPTION VALUE="FreeBSD">FreeBSD<OPTION

VALUE="NetBSD">NetBSD<OPTION VALUE="OpenBSD">OpenBSD<OPTION VALUE="AIX">AIX<OPTION VALUE="BeOS">BeOS<OPTION VALUE="HP-UX">HP-UX<OPTION

VALUE="IRIX">IRIX<OPTION VALUE="Neutrino">Neutrino<OPTION VALUE="OpenVMS">OpenVMS<OPTION VALUE="OS/2">OS/2<OPTION VALUE="OSF/1">OSF/1<OPTION

VALUE="Solaris">Solaris<OPTION VALUE="SunOS">SunOS<OPTION VALUE="other">other</SELECT>

​

</td>

​

​

CS 3240

31 of 76

<td align=left valign=top>

​

<SELECT NAME="op sys" MULTIPLE SIZE=7>

​

<OPTION VALUE="All">All<OPTION VALUE="Windows 3.1">Windows 3.1<OPTION VALUE="Windows 95">Windows 95<OPTION VALUE="Windows 98">Windows 98<OPTION

VALUE="Windows ME">Windows ME<OPTION VALUE="Windows 2000">Windows 2000<OPTION VALUE="Windows NT">Windows NT<OPTION VALUE="Mac System 7">Mac

System 7<OPTION VALUE="Mac System 7.5">Mac System 7.5<OPTION VALUE="Mac System 7.6.1">Mac System 7.6.1<OPTION VALUE="Mac System 8.0">Mac System

8.0<OPTION VALUE="Mac System 8.5">Mac System 8.5<OPTION VALUE="Mac System 8.6">Mac System 8.6<OPTION VALUE="Mac System 9.x">Mac System

9.x<OPTION VALUE="MacOS X">MacOS X<OPTION VALUE="Linux">Linux<OPTION VALUE="BSDI">BSDI<OPTION VALUE="FreeBSD">FreeBSD<OPTION

VALUE="NetBSD">NetBSD<OPTION VALUE="OpenBSD">OpenBSD<OPTION VALUE="AIX">AIX<OPTION VALUE="BeOS">BeOS<OPTION VALUE="HP-UX">HP-UX<OPTION

VALUE="IRIX">IRIX<OPTION VALUE="Neutrino">Neutrino<OPTION VALUE="OpenVMS">OpenVMS<OPTION VALUE="OS/2">OS/2<OPTION VALUE="OSF/1">OSF/1<OPTION

VALUE="Solaris">Solaris<OPTION VALUE="SunOS">SunOS<OPTION VALUE="other">other</SELECT>

​

</td>

​

​

CS 3240

32 of 76

<td align=left valign=top>

​

<SELECT NAME="op sys" MULTIPLE SIZE=7>

​

​

​

​

CS 3240

33 of 76

<td align=left valign=top>

​

<SELECT NAME="op sys" MULTIPLE SIZE=7>

​

​

​

​

CS 3240

34 of 76

<td align=left valign=top>

​

​

​

​

​

CS 3240

35 of 76

<td align=left valign=top>

​

​

​

​

​

CS 3240

36 of 76

​

<SELECT NAME="op sys" MULTIPLE SIZE=7>

​

​

​

​

CS 3240

37 of 76

​

<SELECT NAME="op sys" MULTIPLE SIZE=7>

​

​

​

​

CS 3240

38 of 76

Approach: iterative search

​

Repeat until “small-enough” input causes failure

​

  • Throw away portion of input

​

2. If the output is still wrong go back to 1

​

3. Else go back to previous state and discard other portion.

CS 3240

39 of 76

To this line in ~57 Tests

Ok… so your HTML parser crashed on this input

<td align=left valign=top>

​

<SELECT NAME="op sys" MULTIPLE SIZE=7>

​

<OPTION VALUE="All">All<OPTION VALUE="Windows 3.1">Windows 3.1<OPTION VALUE="Windows 95">Windows 95<OPTION VALUE="Windows 98">Windows 98<OPTION

VALUE="Windows ME">Windows ME<OPTION VALUE="Windows 2000">Windows 2000<OPTION VALUE="Windows NT">Windows NT<OPTION VALUE="Mac System 7">Mac

System 7<OPTION VALUE="Mac System 7.5">Mac System 7.5<OPTION VALUE="Mac System 7.6.1">Mac System 7.6.1<OPTION VALUE="Mac System 8.0">Mac System

8.0<OPTION VALUE="Mac System 8.5">Mac System 8.5<OPTION VALUE="Mac System 8.6">Mac System 8.6<OPTION VALUE="Mac System 9.x">Mac System

9.x<OPTION VALUE="MacOS X">MacOS X<OPTION VALUE="Linux">Linux<OPTION VALUE="BSDI">BSDI<OPTION VALUE="FreeBSD">FreeBSD<OPTION

VALUE="NetBSD">NetBSD<OPTION VALUE="OpenBSD">OpenBSD<OPTION VALUE="AIX">AIX<OPTION VALUE="BeOS">BeOS<OPTION VALUE="HP-UX">HP-UX<OPTION

VALUE="IRIX">IRIX<OPTION VALUE="Neutrino">Neutrino<OPTION VALUE="OpenVMS">OpenVMS<OPTION VALUE="OS/2">OS/2<OPTION VALUE="OSF/1">OSF/1<OPTION

VALUE="Solaris">Solaris<OPTION VALUE="SunOS">SunOS<OPTION VALUE="other">other</SELECT>

​

</td>

​

<td align=left valign=top>

​

<SELECT NAME="priority" MULTIPLE SIZE=7>

​

<OPTION VALUE="--">--<OPTION VALUE="P1">P1<OPTION VALUE="P2">P2<OPTION VALUE="P3">P3<OPTION VALUE="P4">P4<OPTION VALUE="P5">P5</SELECT>

​

</td>

​

<td align=left valign=top>

​

<SELECT NAME="bug severity" MULTIPLE SIZE=7>

​

<OPTION VALUE="blocker">blocker<OPTION VALUE="critical">critical<OPTION VALUE="major">major<OPTION VALUE="normal">normal<OPTION

VALUE="minor">minor<OPTION VALUE="trivial">trivial<OPTION VALUE="enhancement">enhancement</SELECT>

​

</tr>

​

</table>

<SELECT NAME="priority" MULTIPLE SIZE=7>

​

CS 3240

40 of 76

Ok… so your HTML parser crashed on this input

<SELECT NAME="priority" MULTIPLE SIZE=7>

​

CS 3240

41 of 76

Ok… so your HTML parser crashed on this input

<SELECT NAME="priority" MULTIPLE SIZE=7>

​

<SELECT NAME="priori

​

CS 3240

42 of 76

Ok… so your HTML parser crashed on this input

Both pass… what do we do? �Binary search is stuck

<SELECT NAME="priority" MULTIPLE SIZE=7>

​

<SELECT NAME="priori

​

ty" MULTIPLE SIZE=7>

​

CS 3240

43 of 76

Approach: iterative search

​

Repeat until “small-enough” input causes failure

​

  • Throw away portion of input

​

2. If the output is still wrong go back to 1

​

3. Else go back to previous state and discard other portion or regroup

CS 3240

44 of 76

Ok… so your HTML parser crashed on this input

Both pass… what do we do? �Binary search is stuck� Adjust granularity of changes -- not just halving

<SELECT NAME="priority" MULTIPLE SIZE=7>

​

<SELECT NAME="priori

​

ty" MULTIPLE SIZE=7>

​

CS 3240

45 of 76

Approach: iterative binary search

t1

t2

t3

t4

CS 3240

46 of 76

Approach: iterative n-ary search - adjust granularity

t1

t2

t3

t4

t5

t6

tn

Adjust granularity of changes -- not just halving.

More combinations to explore

All sets of 3

All sets of 2

All sets of 1

CS 3240

47 of 76

Approach: iterative n-ary search - adjust granularity

t1

t2

t3

t4

t5

t….

tn

Alternative with even lower granularity

CS 3240

48 of 76

Ok… so your program failed on this input

<SELECT NAME="priority" MULTIPLE SIZE=7>

​

<SELECT NAME="priori

​

ME="priority" MULTIPLE SIZE=7>

​

<SELECT NA ty" MULTIPLE SIZE=7>

​

​

ty" MULTIPLE SIZE=7>

​

Decrease granularity by half

CS 3240

49 of 76

Ok… so your program failed on this input

<SELECT NAME="priority" MULTIPLE SIZE=7>

​

<SELECT NAME="priori

​

ME="priority" MULTIPLE SIZE=7>

​

<SELECT NA ty" MULTIPLE SIZE=7>

​

<SELECT NA LE SIZE=7>

​

​

​

​

ty" MULTIPLE SIZE=7>

​

CS 3240

50 of 76

Ok… so your program failed on this input

<SELECT NAME="priority" MULTIPLE SIZE=7>

​

<SELECT NAME="priori

​

ME="priority" MULTIPLE SIZE=7>

​

<SELECT NA ty" MULTIPLE SIZE=7>

​

<SELECT NA LE SIZE=7>

​

<SELECT NA

​

ty" MULTIPLE SIZE=7>

​

CS 3240

51 of 76

Ok… so your program failed on this input

<SELECT NAME="priority" MULTIPLE SIZE=7>

​

<SELECT NAME="priori

​

ME="priority" MULTIPLE SIZE=7>

​

<SELECT NA ty" MULTIPLE SIZE=7>

​

<SELECT NA LE SIZE=7>

​

<SELECT NA

​

ty" MULTIPLE SIZE=7>

​

… several more iterations ...

<SELECT >

CS 3240

52 of 76

Q: Impact of delta granularity choice?

​

  • Probability of finding subset of input causing failure
  • Speed to explore space of changes

CS 3240

53 of 76

Approach: iterative search

​

n = 2 # n is granularity

while len(input) >= 2:

start = 0

subset_length = len(input) / n

some_complement_is_failing = False

while start < len(input):

complement = input[:int(start)] + input[int(start + subset_length):]

if runProgramWith(complement) == FAIL:

input = complement

n = max(n - 1, 2)

some_complement_is_failing = True

break

start += subset_length

if not some_complement_is_failing:

if n == len(input):

break

n = min(n * 2, len(input))

return input

Best case as good as binary search O(log2n)

Worst case O(n2) - Adapted from A. Zeller

CS 3240

54 of 76

Refinements

​

Wasted cycles on invalid HTML

​

<SELECT NAME="priority" MULTIPLE SIZE=7>

​

<SELECT NAME="priori

​

ME="priority" MULTIPLE SIZE=7>

​

<SELECT NA ty" MULTIPLE SIZE=7>

​

<SELECT NA LE SIZE=7>

​

<SELECT NA

​

ty" MULTIPLE SIZE=7>

​

CS 3240

55 of 76

Refinements

Wasted cycles on invalid HTML

​

<SELECT NAME="priority" MULTIPLE SIZE=7>

​

<SELECT NAME="priori

​

ME="priority" MULTIPLE SIZE=7>

​

<SELECT NA ty" MULTIPLE SIZE=7>

​

<SELECT NA LE SIZE=7>

​

<SELECT NA

​

ty" MULTIPLE SIZE=7>

​

CS 3240

56 of 76

Refinements

Wasted cycles on invalid HTML

Need domain-specific approaches that generate valid inputs

<SELECT NAME="priority" MULTIPLE SIZE=7>

​

<SELECT NAME="priori

​

ME="priority" MULTIPLE SIZE=7>

​

<SELECT NA ty" MULTIPLE SIZE=7>

​

<SELECT NA LE SIZE=7>

​

<SELECT NA

​

ty" MULTIPLE SIZE=7>

​

CS 3240

57 of 76

From Failure Simplification to Culprits

​

​

  • Delta debugging
    • Simplify inputs -- keep code constant
      • Minimal tests that expose fault
    • Simplify code -- keep input constant
      • Faulty code causing the failures

CS 3240

58 of 76

Delta debugging examples

​

​

  • bug.c crashes GCC 2.95.2 when optimization enabled
  • Goal: minimize this program to file a bug report
  • For GCC, a trivial passing run is an empty program

​

What would be the simplification procedure?

​

#define SIZE 20

double mult(double z[], int n) {

int i, j;

i = 0;

for (j = 0; j < n; j++) {

i = i + j + 1;

z[i] = z[i] * (z[0] + 1.0);

}

return z[n];

}

void copy(double to[], double from[], int count) {

int n = (count + 7) / 8;

switch (count % 8) do {

case 0: *to++ = *from++;

case 7: *to++ = *from++;

case 6: *to++ = *from++;

case 5: *to++ = *from++;

case 4: *to++ = *from++;

case 3: *to++ = *from++;

case 2: *to++ = *from++;

case 1: *to++ = *from++;

} while (--n > 0);

return mult(to, 2);

}

int main(int argc, char *argv[]) {

double x[SIZE], y[SIZE];

double *px = x;

while (px < x + SIZE)

*px++ = (px – x) * (SIZE + 1.0);

return copy(y, x, SIZE)

}

Adapted from A. Zeller DD

CS 3240

59 of 76

Delta debugging examples

​

​

#define SIZE 20

double mult(double z[], int n) {

int i, j;

i = 0;

for (j = 0; j < n; j++) {

i = i + j + 1;

z[i] = z[i] * (z[0] + 1.0);

}

return z[n];

}

void copy(double to[], double from[], int count) {

int n = (count + 7) / 8;

switch (count % 8) do {

case 0: *to++ = *from++;

case 7: *to++ = *from++;

case 6: *to++ = *from++;

case 5: *to++ = *from++;

case 4: *to++ = *from++;

case 3: *to++ = *from++;

case 2: *to++ = *from++;

case 1: *to++ = *from++;

} while (--n > 0);

return mult(to, 2);

}

int main(int argc, char *argv[]) {

double x[SIZE], y[SIZE];

double *px = x;

while (px < x + SIZE)

*px++ = (px – x) * (SIZE + 1.0);

return copy(y, x, SIZE)

}

CS 3240

60 of 76

Delta debugging examples

​

​

double mult(double z[], int n) {

int i, j;

i = 0;

for (j = 0; j < n; j++) {

i = i + j + 1;

z[i] = z[i] * (z[0] + 1.0);

}

return z[n];

}

#define SIZE 20

double mult(double z[], int n) {

int i, j;

i = 0;

for (j = 0; j < n; j++) {

i = i + j + 1;

z[i] = z[i] * (z[0] + 1.0);

}

return z[n];

}

void copy(double to[], double from[], int count) {

int n = (count + 7) / 8;

switch (count % 8) do {

case 0: *to++ = *from++;

case 7: *to++ = *from++;

case 6: *to++ = *from++;

case 5: *to++ = *from++;

case 4: *to++ = *from++;

case 3: *to++ = *from++;

case 2: *to++ = *from++;

case 1: *to++ = *from++;

} while (--n > 0);

return mult(to, 2);

}

int main(int argc, char *argv[]) {

double x[SIZE], y[SIZE];

double *px = x;

while (px < x + SIZE)

*px++ = (px – x) * (SIZE + 1.0);

return copy(y, x, SIZE)

}

CS 3240

61 of 76

Delta debugging examples

​

​

double mult(double z[], int n) {

int i, j;

i = 0;

for (j = 0; j < n; j++) {

i = i + j + 1;

z[i] = z[i] * (z[0] + 1.0);

}

return z[n];

}

#define SIZE 20

double mult(double z[], int n) {

int i, j;

i = 0;

for (j = 0; j < n; j++) {

i = i + j + 1;

z[i] = z[i] * (z[0] + 1.0);

}

return z[n];

}

void copy(double to[], double from[], int count) {

int n = (count + 7) / 8;

switch (count % 8) do {

case 0: *to++ = *from++;

case 7: *to++ = *from++;

case 6: *to++ = *from++;

case 5: *to++ = *from++;

case 4: *to++ = *from++;

case 3: *to++ = *from++;

case 2: *to++ = *from++;

case 1: *to++ = *from++;

} while (--n > 0);

return mult(to, 2);

}

int main(int argc, char *argv[]) {

double x[SIZE], y[SIZE];

double *px = x;

while (px < x + SIZE)

*px++ = (px – x) * (SIZE + 1.0);

return copy(y, x, SIZE)

}

t(double z[],int n){int i,j;for(;;){i=i+j+1;z[i]=z[i]*(z[0]+0);}return z[n];}

+700 tests later

CS 3240

62 of 76

Delta Debugging Applicability

​

​

  • Failure inducing input
  • Failure inducing code changes
  • Failure inducing states
  • …

CS 3240

63 of 76

Delta Debugging Challenges

​

​

​

​

CS 3240

64 of 76

Delta Debugging Challenges

​

​

  • Systems with high test-execution costs
  • Systems when changes have unintended side-effects that matter (e.g., change to affect timings)
  • Non-deterministic failures
  • Systems or inputs that cannot be partitioned and replayed

​

​

​

CS 3240

65 of 76

Probabilistic ways to find the culprits

CS 3240

66 of 76

Spectrum-based Localization

  • Insight
    • Executing faulty statement increases chances of failure
    • Not executing faulty line decreases chances of failure
  • Estimation of fault location based on
    • Test results and coverage

CS 3240

67 of 76

Spectrum-based Localization

For each program statement count

ep: # passing tests executing statement

ef: # failing tests executing statement

Compute Statement Risk =

​

ef / (ef + ep)

CS 3240

68 of 76

Spectrum-based Localization

Where is the fault?

CS 3240

69 of 76

Spectrum-based Localization

Jones et al. Tarantula

⅙

⅙

⅙

¼

0

⅓

½

0

0

0

0

0

⅙

​

ef / (ef + ep)

4

4

4

3

5

2

1

5

5

5

5

5

4

​

CS 3240

70 of 76

Spectrum-based Localization

Jones et al. Tarantula

⅙

⅙

⅙

¼

0

⅓

½

0

0

0

0

0

⅙

​

ef / (ef + ep)

4

4

4

3

5

2

1

5

5

5

5

5

4

​

CS 3240

71 of 76

Spectrum-based Localization

For each program statement count

ep: # passing tests executing statement

ef: # failing tests executing statement

nf: # failing tests not executing statement

Compute Statement Risk =

​

ef / (ef + nf)

CS 3240

72 of 76

Spectrum-based Localization

For each program statement count

ep: # passing tests executing statement

ef: # failing tests executing statement

np: # passing tests not executing statement

nf: # failing tests not executing statement

Compute Statement Risk =

​

(ef / (ef + nf))

(ep / (ep + np))+ (ef / (ef + nf))

​

CS 3240

73 of 76

CS 3240

74 of 76

Spectrum-based Localization

Jones et al. Tarantula

CS 3240

75 of 76

Spectrum-based Localization

Jones et al. Tarantula

CS 3240

76 of 76

What we learned

  • Delta Debugging
    • Simple algorithm renders significant simplification
    • Can require many tests -- so they better be fast
    • Needs domain tailoring (reasonable deltas)
  • Statistical analysis for finding culprits
    • Simpler/faster algorithms to detect suspicious statements
    • There may be many suspicious statements

​

​

​

CS 3240