As pairwise ranking becomes broadly employed for elections, sports competitions, recommendations, and so on, attackers have strong motivation and incentives to manipulate the ranking list. They could inject malicious comparisons into the training data to fool the victim. Such a technique is called poisoning attack in regression and classification tasks. In this paper, to the best of our knowledge, we initiate the first systematic investigation of data poisoning attacks on pairwise ranking algorithms, which can be formalized as the dynamic and static games between the ranker and the attacker and can be modeled as certain kinds of integer programming problems. To break the computational hurdle of the underlying integer programming problems, we reformulate them into the distributionally robust optimization (DRO) problems, which are computationally tractable. Based on such DRO formulations, we propose two efficient poisoning attack algorithms and establish the associated theoretical guarantees. The effectiveness of the suggested poisoning attack strategies is demonstrated by a series of toy simulations and several real data experiments. These experimental results show that the proposed methods can significantly reduce the performance of the ranker in the sense that the correlation between the true ranking list and the aggregated results can be decreased dramatically.
翻译:随着对等排名被广泛用于选举、体育竞赛、建议等等,攻击者有强大的动力和动力来操纵排名列表。他们可以在培训数据中插入恶意比较,以欺骗受害者。这种技术被称为回归和分类任务中的中毒攻击。在本文中,我们据我们所知,我们开始对对对等排名算法的数据中毒攻击进行首次系统调查,这种算法可以正式确定为排名者和攻击者之间的动态和静态游戏,可以作为某些类型的整数编程问题。为了打破潜在的整数编程问题的计算障碍,我们将它们重新纳入可计算到的分布性强的优化(DRO)问题。根据这种DRO的配方,我们建议两种有效的中毒攻击算法,并确立相关的理论保证。建议的中毒攻击策略的有效性通过一系列玩具模拟和若干真正的数据实验得到证明。这些实验结果表明,拟议的方法可以显著降低排名员的性能,因为真正的排名列表和汇总结果之间的关联性可以大幅下降。