Parameter perturbations in dynamical models of biochemical networks affect the qualitative dynamical behaviour observed in the model. Since this qualitative behaviour is in many cases the key model output used to explain biological function, the robustness analysis of the model's behaviour with respect to parametric uncertainty is a crucial step in systems biology research. In this paper, we develop a new method for robustness analysis of the dynamical behaviour. As a first step, we provide a characterization of non-robust perturbations as a system of polynomial equalities and inequalities. In the second step, we apply the Positivstellensatz and Handelman representation of polynomials to check for the non-existence of solutions to this system, which can be relaxed to solving a linear program. Thereby, a solution to the linear program yields a robustness certificate for the considered dynamical behaviour. With these robustness certificates, we propose an algorithm to compute a lower robustness bound corresponding to a level of parametric uncertainty up to which no local bifurcations can occur. The applicability of the proposed method to biochemical network models is illustrated by analysing the robustness of oscillations in a model of the NF-kappa B signalling pathway. The results may be used to define a level of confidence in the observed model behaviour under parametric uncertainty, making them valuable for evaluating dynamical models of biological networks. (C) 2011 Elsevier Ltd. All rights reserved.