  Social network alignment (SNA) holds significant importance for various
downstream applications, prompting numerous professionals to develop and share
SNA tools. Unfortunately, these tools can be exploited by malicious actors to
integrate sensitive user information, posing cybersecurity risks. While many
researchers have explored attacking SNA (ASNA) through a network modification
attack way, practical feasibility remains a challenge. This paper introduces a
novel approach, the node injection attack. To overcome the problem of modeling
and solving within a limited time and balancing costs and benefits, we propose
a low-cost, high-impact node injection attack via dynamic programming (DPNIA)
framework. DPNIA models ASNA as a problem of maximizing the number of confirmed
incorrect correspondent node pairs who have a greater similarity scores than
the pairs between existing nodes, making ASNA solvable. Meanwhile, it employs a
cross-network evaluation method to identify node vulnerability, facilitating a
progressive attack from easy to difficult. Additionally, it utilizes an optimal
injection strategy searching method, based on dynamic programming, to determine
which links should be added between injected nodes and existing nodes, thereby
achieving a high impact for attack effectiveness at a low cost. Experiments on
four real-world datasets consistently demonstrate that DPNIA consistently and
significantly outperforms various attack baselines.
