Most software systems evolve over time to adapt to changing environment, needs, new concepts, new technologies and standards. Modification to the software is inevitable in software evolution and may be through growth in the number of functions, components and interfaces, or alteration of existing modules. Examples commonly seen are changes or upgrades in operating systems, browsers, communication software. Software maintenance to understand, implement and validate changes is a very expensive activity and costs billions of dollars each year in the software industry. In this proposal, we focus on the problem of validating changes and their effects. This is typically carried out using regression testing, defined as ``selective retesting of a system or component to verify that modifications have not caused unintended effects and that the system or component still complies with its specified requirements'' Regression testing is an expensive and time consuming process and accounts for majority of the maintenance costs. Balancing confidence in the software correctness (gained from extensive and frequent regression testing) against cost of regression test effort is one of the major challenges in software maintenance. Estimates of regression test cost will help developers and managers in achieving this balance. Accurate regression test cost estimates are crucial for planning project schedules, allocating resources, software reliability, monitoring and control. Cost models estimating maintenance effort and development effort have been developed in the past. Nevertheless, these models cannot be used since crucial elements for predicting test effort such as testing requirements, test cases, test quality metrics are ignored for the most part in these models. Our goal in this proposal is to define a model that accurately estimates regression test cost for evolving software taking into account effects of changes on software behaviour, testing requirements, industry and process specific information, and quality metrics to be satisfied. At the end of this proposal, we will have tools that when given the software changes and quality requirements as inputs can predict the cost of validating the changes. We will evaluate the test effort estimates on large open-source software evolution repositories such as DEBIAN GNU/Linux distribution releases and OpenSSH. We will also collaborate with IBM and evaluate our estimates on their software. The prototype analysis tools that we develop during the course of the project will be made freely available in open-source form. We will package and ship our analysis tools as part of well-established distributions such as Debian. This will allow numerous developers of large-scale software (including our project partner) to directly apply our techniques to their problems, improving their development and maintenance processes.