  Software-Defined-eXchanges (SDXes) promise to tackle the timely quest of
bringing improving the inter-domain routing ecosystem through SDN deployment.
Yet, the naive deployment of SDN on the Internet raises concerns about the
correctness of the inter-domain data-plane. By allowing operators to deflect
traffic from the default BGP route, SDN policies are susceptible of creating
permanent forwarding loops invisible to the control-plane.
  In this paper, we propose a system, called Prelude, for detecting SDN-induced
forwarding loops between SDXes with high accuracy without leaking the private
routing information of network operators. To achieve this, we leverage Secure
Multi-Party Computation (SMPC) techniques to build a novel and general
privacy-preserving primitive that detects whether any subset of SDN rules might
affect the same portion of traffic without learning anything about those rules.
We then leverage that primitive as the main building block of a distributed
system tailored to detect forwarding loops among any set of SDXes. We leverage
the particular nature of SDXes to further improve the efficiency of our SMPC
solution.
  The number of valid SDN rules, i.e., not creating loops, rejected by our
solution is 100x lower than previous privacy-preserving solutions, and also
provides better privacy guarantees. Furthermore, our solution naturally
provides network operators with some hindsight on the cost of the deflected
paths.
