  Uneven terrain necessarily transforms periodic walking into a non-periodic
motion. As such, traditional stability analysis tools no longer adequately
capture the ability of a bipedal robot to locomote in the presence of such
disturbances. This motivates the need for analytical tools aimed at generalized
notions of stability -- robustness. Towards this, we propose a novel definition
of robustness, termed \emph{$\delta$-robustness}, to characterize the domain on
which a nominal periodic orbit remains stable despite uncertain terrain. This
definition is derived by treating perturbations in ground height as
disturbances in the context of the input-to-state-stability (ISS) of the
extended Poincar\'{e} map associated with a periodic orbit. The main theoretic
result is the formulation of robust Lyapunov functions that certify
$\delta$-robustness of periodic orbits. This yields an optimization framework
for verifying $\delta$-robustness, which is demonstrated in simulation with a
bipedal robot walking on uneven terrain.
