T09 · Insecure Skill Coding Practices
- Location
scripts/negotiator.py:42- Finding
Unbounded Shapley Permutation Computation Enables Denial of Service
- Content
View full analysis
Vulnerability Details
File Location:
scripts/negotiator.py, lines 42–52; reachable from lines 88–91
Vulnerability Type: Uncontrolled resource consumption
Risk Level: MediumVulnerable Code
python def shapley(players, char_func): """char_func(subset frozenset)->实数贡献值。返回每玩家平均边际贡献。""" n = len(players) vals = {p: 0.0 for p in players} for perm in itertools.permutations(players): seen = frozenset() for i, p in enumerate(perm): contrib = char_func(seen | {p}) - char_func(seen) vals[p] += contrib seen = seen | {p} fact = _factorial(n) return {p: vals[p] / fact for p in players}The vulnerable function is directly reachable through user-controlled command-line JSON:
python elif a.mode == "shapley": players = kw["players"] cf = lambda s: (kw["char"][",".join(sorted(s))] if s else 0.0) print(json.dumps(shapley(players, cf), ensure_ascii=False))Technical Analysis
The Shapley implementation exhaustively enumerates every permutation of the user-supplied
playerslist. Fornplayers, it processesn!permutations and performs up tonmarginal-contribution calculations for each permutation, resulting in approximatelyO(n × n!)work.Neither the CLI entry point nor
shapley()limits the number of players, enforces a computational budget, or switches to bounded sampling for large inputs. AlthoughSKILL.mdwarns that complexity is exponential and suggests sampling above approximately 12 players, that limitation is not enforced in code.An attacker who can control the JSON supplied to the command can therefore provide a sufficiently large player list and matching characteristic-function entries. Enumeration begins lazily but consumes extreme CPU time as the list grows, tying up the process until it is terminated or completes.
Attack Path
- The attacker gains the ability to submit input to an integration that invokes `negotiator. ...[truncated 1018 chars]
- Remediation
View remediation
Remediation Suggestions
- Enforce a conservative maximum player count before permutation enumeration. Reject larger exact-computation requests with a clear error.
- Implement an approximate Shapley algorithm based on a bounded number of randomly sampled permutations for larger games.
- Place explicit limits on iterations, execution time, input size, and coalition-map size.
- Validate that
playersis a list of unique, bounded-length identifiers and that all required characteristic-function values are finite numeric values. - Expose exact and approximate modes explicitly so callers understand the accuracy and resource tradeoffs.
- If the Skill is exposed through a service, add request timeouts, CPU or process quotas, concurrency limits, and rate limiting as defense-in-depth.
- Add tests confirming that oversized inputs are rejected or processed through the bounded approximation path.
A minimal guard for exact evaluation could follow this pattern:
python MAX_EXACT_PLAYERS = 10 def shapley(players, char_func): if not isinstance(players, list): raise ValueError("players must be a list") if len(players) > MAX_EXACT_PLAYERS: raise ValueError( f"Exact Shapley computation supports at most " f"{MAX_EXACT_PLAYERS} players" ) if len(set(players)) != len(players): raise ValueError("players must be unique") n = len(players) vals = {p: 0.0 for p in players} for perm in itertools.permutations(players): seen = frozenset() for p in perm: contrib = char_func(seen | {p}) - char_func(seen) vals[p] += contrib seen = seen | {p} fact = _factorial(n) return {p: vals[p] / fact for p in players}
