A.: Bias-variance tradeoffs in program analysis

It is often the case that increasing the precision of a program anal-ysis leads to worse results. It is our thesis that this phenomenon is domains as the basis for inferring strong invariants of programs. We show that bias-variance tradeoffs, an idea from learning theory, can be used to explain why more precise abstractions do not necessarily lead to better results and also provides practical techniques for cop-ing with such limitations. Learning theory captures precision using a combinatorial quantity called the VC dimension. We compute the VC dimension for different abstractions and report on its useful-ness as a precision metric for program analyses. We evaluate cross validation, a technique for addressing bias-variance tradeoffs, on an industrial strength program verification tool called YOGI. The tool produced using cross validation has significantly better run-ning time, finds new defects, and has fewer time-outs than the cur-rent production version. Finally, we make some recommendations for tackling bias-variance tradeoffs in program analysis