CCF:Small:Algorithmic Fraud Detection

CCF:Small：算法欺诈检测

• 批准号: 2221980
• 负责人: Seth Pettie
• 金额: $ 49.92万
• 依托单位: Regents of the University of Michigan - Ann Arbor
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2022
• 资助国家: 美国
• 起止时间: 2022-10-01 至 2025-09-30
• 项目状态: 未结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2221980&HistoricalAwards=false
• 关键词: 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.

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

项目成果

Byzantine Agreement with Optimal Resilience via Statistical Fraud Detection

通过统计欺诈检测实现具有最佳弹性的拜占庭协议

• 发表时间: 2023
• 期刊: SIAM Symposium on Discrete Algorithms
• 作者: Shang-En Huang, Seth Pettie

Better Cardinality Estimators for HyperLogLog, PCSA, and Beyond

• DOI: 10.1145/3584372.3588680
• 发表时间: 2023-06
• 期刊: Proceedings of the 42nd ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems
• 作者: Dingyu Wang;Seth Pettie

Fully Dynamic Connectivity in $O(\log n(\log\log n)^2)$ Amortized Expected Time

$O(log n(loglog n)^2)$ 摊销预期时间中的完全动态连接

• DOI: 10.46298/theoretics.23.6
• 发表时间: 2023
• 期刊: TheoretiCS
• 作者: Huang, Shang-En;Huang, Dawei;Kopelowitz, Tsvi;Pettie, Seth;Thorup, Mikkel
• 通讯作者: Thorup, Mikkel

Almost Optimal Exact Distance Oracles for Planar Graphs

平面图的近乎最优精确距离预言

• DOI: 10.1145/3580474
• 发表时间: 2023
• 期刊: Journal of the ACM
• 影响因子: 2.5
• 作者: Charalampopoulos, Panagiotis;Gawrychowski, Paweł;Long, Yaowei;Mozes, Shay;Pettie, Seth;Weimann, Oren;Wulff-Nilsen, Christian
• 通讯作者: Wulff-Nilsen, Christian