CCF:Small:Algorithmic Fraud Detection

欺诈是一个普遍存在于人类活动所有领域的问题，在这些领域，欺诈的动机足够强烈，而检测方法足够薄弱。欺诈在金融交易、保险索赔等方面很明显，但互联网开辟了全新的欺诈形式，如点击欺诈和声誉欺诈，并帮助使旧形式的欺诈自动化。 大多数现代欺诈检测工作都是统计性的。 他们寻找交易记录中的统计异常，这些异常以某种方式偏离已知或合理的分布。 这种类型的欺诈检测通常是专门针对一个应用程序的，并且通常没有正式的数学保证。 在未来，欺诈行为将更加自动化，欺诈的主体本身往往是某种计算机系统。这个项目的目标是开发一个抽象的，非特定领域的算法和统计欺诈检测理论。 研究人员将开发算法欺诈检测的一般方法，这些方法的效率和有效性有正式的保证。该项目考虑多方欺诈检测游戏，这是一种迭代随机游戏，其中敌对方必须通过伪造随机位来重复实现期望的结果（例如，修复共享的硬币翻转的结果）-但仍然未被检测到。 诚实方的目标是检测何时发生敌对操纵，并有效可靠地识别特定的敌对方。 这个框架是通用的，足以适用于许多问题和领域。 该项目的最初目标是研究抽象的欺诈检测游戏（抛硬币游戏，随机游走游戏，分配游戏，领导者选举游戏），并通过统计欺诈检测的透镜重新审视现有的算法挑战。 研究人员将设计一个拜占庭协议协议，使用统计欺诈检测测试来发现行为不端的过程，具有最佳的弹性。 欺诈检测的想法将被用来保护随机蒙特卡罗数据结构，其内部的随机性是部分泄漏。这个奖项反映了NSF的法定使命，并已被认为是值得通过使用基金会的智力价值和更广泛的影响审查标准进行评估的支持。

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.