Outsourcing of certification predates homeland security - see e.g. mid-90s reporting on the 777 certification[1]. In fact, the idea of outsourcing parts of the certification process started IIRC in the mid-1940s. What did happen past 2001 (but not due to budget pressures) is that the airline manufacturers got the authority to appoint their own designees, and were allowed to self-certify.

Not for budget reasons, but for "deregulation is good" reasons. The money isn't gone. We've just got people who'd like "a government so small they can drown it in a bathtub". Well, it's drowning alright.

[1] http://community.seattletimes.nwsource.com/archive/?date=199...