Fastställande av om ett visst program uppfyller en given gräns på den mängd resurser som det kan använda är ett grundläggande problem med kritiska praktiska tillämpningar. Konventionella automatiska kontrollörer för säkerhetsegenskaper kan inte tillämpas för att ta itu med detta problem direkt eftersom sådana kontrollörer målegenskaper uttryckta i decledable teorier; dock många praktiska gränser uttrycks i icke-linjära teorier, som är obeslutbara. I detta arbete introducerar vi en automatisk verifieringsalgoritm, CAMPY, som avgör om ett givet program P uppfyller en given resurs bunden B, som kan uttryckas med polynom, exponentiell, och logaritmiska termer. Det viktigaste tekniska bidraget bakom vår kontrollör är en interpoleringsteori för icke-linjära teorier som lazily lär sig en tillräckligt exakt approximation av icke-linjära teorier genom att selektivt jorda teorem av den ickelinjära teorin som är relevanta för att bevisa att P uppfyller B. För att utvärdera CAMPY, implementerade vi det för att rikta Java Virtual Machine bytecode. Vi tillämpade CAMPY för att verifiera att över 20 lösningar som lämnats in för programmeringsproblem på populära online-kodningsplattformar uppfyller eller inte uppfyller förväntade komplexitetsgränser.
REF hanterade icke-linjära teorier genom att lazily förhala teorem som är tillräckliga för att approximera en icke-linjär teori.
Complexity verification using guided theorem enumeration
{'venue': 'POPL 2017', 'journal': None, 'mag_field_of_study': ['Computer Science']}