CCF:Small:Algorithmic Fraud Detection

点击翻译按钮获取中文摘要

Fraud is a pervasive problem in all areas of human activity where the incentives are strong enough to cheat and the methods of detection sufficiently weak. Fraud is evident in financial transactions, insurance claims, and such, but the internet has opened up entirely new forms of fraud such as click-fraud and reputation fraud, and helped to automate older forms of fraud. Most modern fraud-detection efforts are statistical. They look for statistical anomalies in transaction records that deviate in some way from known or plausible distributions. This type of fraud detection is usually ad hoc, specialized to one application, and typically has no formal mathematical guarantees. In the future there will be more automation in the perpetration of frauds, and the subject of the fraud will itself frequently be some computer system. The goal of this project is to develop an abstract, non-domain-specific theory of algorithmic and statistical fraud detection. The investigator will develop general methods for algorithmic fraud detection that have formal guarantees on their efficiency and efficacy.This project considers multi-party fraud detection games, which are iterated randomized games in which the adversarial parties must repeatedly achieve a desired outcome (say, fixing the outcome of a shared coin flip) by forging their random bits --- and yet remain undetected. It is the goal of the honest parties to detect when adversarial manipulation is taking place, and to identify specific adversarial parties, efficiently and reliably. This framework is general enough to apply to many problems and domains. The initial goals of the project are to study abstract fraud detection games (coin flipping games, random walk games, allocation games, leader election games), and to revisit existing algorithmic challenges through the lens of statistical fraud detection. The investigator will design a Byzantine agreement protocol with optimal resilience using statistical fraud detection tests to discover misbehaving processes. Fraud detection ideas will be used to protect randomized Monte Carlo data structures whose internal randomness is partially leaked.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.