Static Analysis to ImproveSoftware QualityJeff Foster Mike HicksUniversity of Maryland2Software Quality Today-- Bill Gates, January 15, 2002(highest priority for Microsoft)Trustworthy Computing is computing that is available,reliable, and secure as electricity, water services andtelephony....No Trustworthy Computing platform existstoday.-- NIST Planning Report 02-3, May 2002[T]he national annual costs of an inadequate infrastructurefor software testing is estimated to range from $22.2 to$59.5 billion.3Conclusions?• Software is buggy– It’s hard to ensure that it’s reliable– ...and doing so is important4Current Practice• Testing– Make sure program runs correctly on set of inputs– Drawbacks: Expensive, difficult, hard to cover allcode paths, no guaranteesinputs outputsprogramIs it correct?oracle register char *q; char inp[MAXLINE]; char cmdbuf[MAXLINE]; extern ENVELOPE BlankEnvelope; extern void help __P((char *)); extern void settime __P((ENVELOPE *)); extern bool enoughdiskspace __P((long)); extern int runinchild __P((char *, ENVELOPE *));...5Current Practice (cont’d)• Code Auditing– Convince someone else your source code is correct– Drawbacks: Expensive, hard, no guarantees??? register char *q; char inp[MAXLINE]; char cmdbuf[MAXLINE]; extern ENVELOPE BlankEnvelope; extern void help __P((char *)); extern void settime __P((ENVELOPE *)); extern bool enoughdiskspace __P((long)); extern int runinchild __P((char *, ENVELOPE *)); extern void checksmtpattack __P((volatile int *, int, char *, ENVELOPE *)); if (fileno(OutChannel) != fileno(stdout)) { /* arrange for debugging output to go to remote host */ (void) dup2(fileno(OutChannel), fileno(stdout)); } settime(e); peerhostname = RealHostName; if (peerhostname == NULL) peerhostname = "localhost"; CurHostName = peerhostname; CurSmtpClient = macvalue('_', e); if (CurSmtpClient == NULL) CurSmtpClient = CurHostName; setproctitle("server %s startup", CurSmtpClient);#if DAEMON if (LogLevel > 11) { /* log connection information */ sm_syslog(LOG_INFO, NOQID, "SMTP connect from %.100s (%.100s)", CurSmtpClient, anynet_ntoa(&RealHostAddr)); }#endif /* output the first line, inserting "ESMTP" as second word */ expand(SmtpGreeting, inp, sizeof inp, e); p = strchr(inp, '\n'); if (p != NULL) *p++ = '\0'; id = strchr(inp, ' '); if (id == NULL) id = &inp[strlen(inp)]; cmd = p == NULL ? "220 %.*s ESMTP%s" : "220-%.*s ESMTP%s"; message(cmd, id - inp, inp, id); /* output remaining lines */ while ((id = p) != NULL && (p = strchr(id, '\n')) != NULL) { *p++ = '\0'; if (isascii(*id) && isspace(*id)) cmd < &cmdbuf[sizeof cmdbuf - 2]) *cmd++ = *p++; *cmd = '\0'; /* throw away leading whitespace */ while (isascii(*p) && isspace(*p)) p++; /* decode command */ for (c = CmdTab; c->cmdname != NULL; c++) { if (!strcasecmp(c->cmdname, cmdbuf)) break; } /* reset errors */ errno = 0; /* ** Process command. ** ** If we are running as a null server, return 550 ** to everything. */ if (nullserver) { switch (c->cmdcode) { case CMDQUIT: case CMDHELO: case CMDEHLO: case CMDNOOP: /* process normally */ break; default: if (++badcommands > MAXBADCOMMANDS) sleep(1); usrerr("550 Access denied"); continue; } } /* non-null server */ switch (c->cmdcode) { case CMDMAIL: case CMDEXPN: case CMDVRFY: while (isascii(*p) && isspace(*p)) p++; if (*p == '\0') break; kp = p; /* skip to the value portion */ while ((isascii(*p) && isalnum(*p)) || *p == '-') p++; if (*p == '=') { *p++ = '\0'; vp = p; /* skip to the end of the value */ while (*p != '\0' && *p != ' ' && !(isascii(*p) && iscntrl(*p)) && *p != '=') p++; } if (*p != '\0') *p++ = '\0'; if (tTd(19, 1)) printf("RCPT: got arg %s=\"%s\"\n", kp, vp == NULL ? "<null>" : vp); rcpt_esmtp_args(a, kp, vp, e); if (Errors > 0) break; } if (Errors > 0) break; /* save in recipient list after ESMTP mods */ a = recipient(a, &e->e_sendqueue, 0, e); if (Errors > 0) break; /* no errors during parsing, but might be a duplicate */ e->e_to = a->q_paddr; if (!bitset(QBADADDR, a->q_flags)) { message("250 Recipient ok%s", bitset(QQUEUEUP, a->q_flags) ? " (will queue)" : ""); nrcpts++; } else { /* punt -- should keep message in ADDRESS.... */6And If You’re Worried about Security…A malicious adversary is trying to exploitanything you miss!What more can we do?7Tools for Software Quality• Build tools that analyze source code (staticanalysis)– Reason about all possible runs of the program• Check limited but very useful properties– Eliminate categories of errors– Let people concentrate on the deep reasoning• Develop programming models– Avoid mistakes in the first place– Encourage programmers to think about and makemanifest their assumptions8Oops — We Can’t Do This!• Rice’s Theorem: No computer program canprecisely determine anything interesting aboutarbitrary source code– Does this program terminate?– Does this program produce value 42?– Does this program raise an exception?– Is this program correct?9The Art of Static Analysis• Programmers don’t write arbitrarilycomplicated programs• Programmers have ways to control complexity– Otherwise they couldn’t make sense of them• Target: Be precise for the programs thatprogrammers want to write– It’s OK to forbid yucky code in the name of safety10Research at the University of Maryland• Developed a number of practical toolsaddressing different software quality issues– CQual — User-defined type qualifiers for C– Locksmith — C data race detection– FindBugs — Finding (Java) bugs is easy– Cyclone — Language for safe, low-level programming– Ginseng — Safe updates to running software– Saffire — Type checking multi-lingual programs– Pistachio — Checking network protocolimplementations11CQual: Background• Tools need specificationsspin_lock_irqsave(&tty->read_lock, flags);put_tty_queue_nolock(c, tty);spin_unlock_irqrestore(&tty->read_lock,