Virtual appliances store the required information to instantiate a functional Virtual Machine (VM) on Infrastructure as a Service (IaaS) cloud systems. Large appliance size obstructs IaaS systems to deliver dynamic and scalable infrastructures according to their promise. To overcome this issue, this paper offers a novel technique for virtual appliance developers to publish appliances for the dynamic environments of IaaS systems. Our solution achieves faster virtual machine instantiation by reducing the appliance size while maintaining its key functionality. The new virtual appliance optimization algorithm identifies the removable parts of the appliance. Then, it applies active fault injection to remove the identified parts. Afterward, our solution assesses the functionality of the reduced virtual appliance by applying the-appliance developer provided-validation algorithms. We also introduce a technique to parallelize the fault injection and validation phases of the algorithm. Finally, the prototype implementation of the algorithm is discussed to demonstrate the efficiency of the proposed algorithm through the optimization of two well-known virtual appliances. Results show that the algorithm significantly decreased virtual machine instantiation time and increased dynamism in IaaS systems.