We introduce the general arbitrage-free valuation framework for counterparty risk adjustments in presence of bilateral default risk, including default of the investor. We illustrate the symmetry in the valuation and show that the adjustment involves a long position in a put option plus a short position in a call option, both with zero strike and written on the residual net value of the contract at the relevant default times. We allow for correlation between the default times of the investor, counterparty and underlying portfolio risk factors. We use arbitrage-free stochastic dynamical models. We then specialize our analysis to Credit Default Swaps (CDS) as underlying portfolio, generalizing the work of Brigo and Chourdakis (2008) [5] who deal with unilateral and asymmetric counterparty risk. We introduce stochastic intensity models and a trivariate copula function on the default times exponential variables to model default dependence. Similarly to [5], we find that both default correlation and credit spread volatilities have a relevant and structured impact on the adjustment. Differently from [5], the two parties will now agree on the credit valuation adjustment. We study a case involving British Airways, Lehman Brothers and Royal Dutch Shell, illustrating the bilateral adjustments in concrete crisis situations.