In this paper, we proposed a general framework for data poisoning attacks to\ngraph-based semi-supervised learning (G-SSL). In this framework, we first unify\ndifferent tasks, goals, and constraints into a single formula for data\npoisoning attack in G-SSL, then we propose two specialized algorithms to\nefficiently solve two important cases --- poisoning regression tasks under\n$\\ell_2$-norm constraint and classification tasks under $\\ell_0$-norm\nconstraint. In the former case, we transform it into a non-convex trust region\nproblem and show that our gradient-based algorithm with delicate initialization\nand update scheme finds the (globally) optimal perturbation. For the latter\ncase, although it is an NP-hard integer programming problem, we propose a\nprobabilistic solver that works much better than the classical greedy method.\nLastly, we test our framework on real datasets and evaluate the robustness of\nG-SSL algorithms. For instance, on the MNIST binary classification problem\n(50000 training data with 50 labeled), flipping two labeled data is enough to\nmake the model perform like random guess (around 50\\% error).\n