As an important Cloud feature, security assessment has attracted massive attention in the recent years. However, the broad adoption of Cloud computing and its fast growth are raising critical scalability issues for security assessment frameworks. In this work, we addressed the scalability issue from different perspectives. First, we suggested a decentralized multi-tenant security assessment tool, where both the Cloud Service Providers (CSP) and tenants are able to perform security assessment and mitigation. Secondly, the framework uses analytical stochastic modeling altogether with dynamic programming (here, we use value iteration algorithm) to find the optimal policy concerning the routing of security requests between different execution agents. Thirdly, we designed an iterative heuristic algorithm that helps the CSP to improve the system parameters to get better performance. The simulation results have demonstrated the benefit of using our framework in terms of identifying the optimal routing policy of security requests and improving system configuration.