Taint::getPredecessorPath() - Code Metrics - vimeo/psalm - Measure and Improve Code Quality continuously with Scrutinizer

Taint::getPredecessorPath() A
last analyzed 2020-07-20 09:18 UTC

↳ Parent: Taint

Complexity

Conditions	5
Paths	12

Size

Total Lines

Duplication

Lines	0
Ratio	0 %

Importance

Changes

Metric	Value
cc	5
nc	12
nop	1
dl	0
loc	22
rs	9.2568
c	0
b	0
f	0

<?php

namespace Psalm\Internal\Codebase;

use Psalm\CodeLocation;
use Psalm\Internal\Analyzer\StatementsAnalyzer;
use Psalm\Internal\Provider\ClassLikeStorageProvider;
use Psalm\Internal\Provider\FileReferenceProvider;
use Psalm\Internal\Provider\FileStorageProvider;
use Psalm\Internal\Taint\Path;
use Psalm\Internal\Taint\Sink;
use Psalm\Internal\Taint\Source;
use Psalm\Internal\Taint\TaintNode;
use Psalm\Internal\Taint\Taintable;
use Psalm\IssueBuffer;
use Psalm\Issue\TaintedInput;
use function array_merge;
use function array_merge_recursive;
use function strtolower;
use UnexpectedValueException;
use function count;
use function implode;
use function substr;
use function strlen;
use function array_intersect;
use function strpos;
use function array_reverse;

class Taint
{
    /** @var array<string, Source> */
    private $sources = [];

    /** @var array<string, Taintable> */
    private $nodes = [];

    /** @var array<string, Sink> */
    private $sinks = [];

    /** @var array<string, array<string, Path>> */
    private $forward_edges = [];

    /** @var array<string, array<string, true>> */
    private $specialized_calls = [];

    /** @var array<string, array<string, true>> */
    private $specializations = [];

    public function addSource(Source $node) : void
    {
        $this->sources[$node->id] = $node;
    }

    public function addSink(Sink $node) : void
    {
        $this->sinks[$node->id] = $node;
        // in the rare case the sink is the _next_ node, this is necessary
        $this->nodes[$node->id] = $node;
    }

    public function addTaintNode(TaintNode $node) : void
    {
        $this->nodes[$node->id] = $node;

        if ($node->unspecialized_id && $node->specialization_key) {
            $this->specialized_calls[$node->specialization_key][$node->unspecialized_id] = true;
            $this->specializations[$node->unspecialized_id][$node->specialization_key] = true;
        }
    }

    /**
     * @param array<string> $added_taints
     * @param array<string> $removed_taints
     */
    public function addPath(
        Taintable $from,
        Taintable $to,
        string $path_type,
        ?array $added_taints = null,
        ?array $removed_taints = null
    ) : void {
        $from_id = $from->id;
        $to_id = $to->id;

        if ($from_id === $to_id) {
            return;
        }

        $this->forward_edges[$from_id][$to_id] = new Path($path_type, $added_taints, $removed_taints);
    }

    public function getPredecessorPath(Taintable $source) : string
    {
        $location_summary = '';

        if ($source->code_location) {
            $location_summary = $source->code_location->getShortSummary();
        }

        $source_descriptor = $source->label . ($location_summary ? ' (' . $location_summary . ')' : '');

        $previous_source = $source->previous;

        if ($previous_source) {
            if ($previous_source === $source) {
                return '';
            }

            return $this->getPredecessorPath($previous_source) . ' -> ' . $source_descriptor;
        }

        return $source_descriptor;
    }

    public function getSuccessorPath(Taintable $sink) : string
    {
        $location_summary = '';

        if ($sink->code_location) {
            $location_summary = $sink->code_location->getShortSummary();
        }

        $sink_descriptor = $sink->label . ($location_summary ? ' (' . $location_summary . ')' : '');

        $next_sink = $sink->previous;

        if ($next_sink) {
            if ($next_sink === $sink) {
                return '';
            }

            return $sink_descriptor . ' -> ' . $this->getSuccessorPath($next_sink);
        }

        return $sink_descriptor;
    }

    /**
     * @return list<array{location: ?CodeLocation, label: string, entry_path_type: string}>

     */
    public function getIssueTrace(Taintable $source) : array
    {
        $previous_source = $source->previous;

        $node = [
            'location' => $source->code_location,
            'label' => $source->label,
            'entry_path_type' => \end($source->path_types) ?: ''
        ];

        if ($previous_source) {
            if ($previous_source === $source) {
                return [];
            }

            return array_merge($this->getIssueTrace($previous_source), [$node]);
        }

        return [$node];
    }

    public function addThreadData(self $taint) : void
    {
        $this->sources += $taint->sources;
        $this->sinks += $taint->sinks;
        $this->nodes += $taint->nodes;
        $this->specialized_calls += $taint->specialized_calls;

        foreach ($taint->forward_edges as $key => $map) {
            if (!isset($this->forward_edges[$key])) {
                $this->forward_edges[$key] = $map;
            } else {
                $this->forward_edges[$key] += $map;
            }
        }

        foreach ($taint->specializations as $key => $map) {
            if (!isset($this->specializations[$key])) {
                $this->specializations[$key] = $map;
            } else {
                $this->specializations[$key] += $map;
            }
        }
    }

    public function connectSinksAndSources() : void
    {
        $visited_source_ids = [];

        $sources = $this->sources;
        $sinks = $this->sinks;

        for ($i = 0; count($sinks) && count($sources) && $i < 40; $i++) {
            $new_sources = [];

            foreach ($sources as $source) {
                $source_taints = $source->taints;
                \sort($source_taints);

                $visited_source_ids[$source->id][implode(',', $source_taints)] = true;

                $generated_sources = $this->getSpecializedSources($source);

                foreach ($generated_sources as $generated_source) {
                    $new_sources = array_merge(
                        $new_sources,
                        $this->getChildNodes(
                            $generated_source,
                            $source_taints,
                            $sinks,
                            $visited_source_ids
                        )
                    );
                }
            }

            $sources = $new_sources;
        }
    }

    /**
     * @param array<string> $source_taints
     * @param array<Taintable> $sinks
     * @return array<Taintable>
     */
    private function getChildNodes(
        Taintable $generated_source,
        array $source_taints,
        array $sinks,
        array $visited_source_ids
    ) : array {
        $new_sources = [];

        foreach ($this->forward_edges[$generated_source->id] as $to_id => $path) {
            $path_type = $path->type;
            $added_taints = $path->unescaped_taints ?: [];
            $removed_taints = $path->escaped_taints ?: [];

            if (!isset($this->nodes[$to_id])) {
                continue;
            }

            $new_taints = \array_unique(
                \array_diff(
                    \array_merge($source_taints, $added_taints),
                    $removed_taints
                )
            );

            \sort($new_taints);

            $destination_node = $this->nodes[$to_id];

            if (isset($visited_source_ids[$to_id][implode(',', $new_taints)])) {
                continue;
            }

            if (self::shouldIgnoreFetch($path_type, 'array', $generated_source->path_types)) {
                continue;
            }

            if (self::shouldIgnoreFetch($path_type, 'property', $generated_source->path_types)) {
                continue;
            }

            if (isset($sinks[$to_id])) {
                $matching_taints = array_intersect($sinks[$to_id]->taints, $new_taints);

                if ($matching_taints && $generated_source->code_location) {
                    $config = \Psalm\Config::getInstance();

                    if ($sinks[$to_id]->code_location
                        && $config->reportIssueInFile('TaintedInput', $sinks[$to_id]->code_location->file_path)
                    ) {
                        $issue_location = $sinks[$to_id]->code_location;
                    } else {
                        $issue_location = $generated_source->code_location;
                    }

                    if (IssueBuffer::accepts(
                        new TaintedInput(
                            'Detected tainted ' . implode(', ', $matching_taints),
                            $issue_location,
                            $this->getIssueTrace($generated_source),
                            $this->getPredecessorPath($generated_source)
                                . ' -> ' . $this->getSuccessorPath($sinks[$to_id])
                        )
                    )) {
                        // fall through
                    }

                    continue;
                }
            }

            $new_destination = clone $destination_node;
            $new_destination->previous = $generated_source;
            $new_destination->taints = $new_taints;
            $new_destination->specialized_calls = $generated_source->specialized_calls;
            $new_destination->path_types = array_merge($generated_source->path_types, [$path_type]);

            $new_sources[$to_id] = $new_destination;
        }

        return $new_sources;
    }

    /** @param array<string> $previous_path_types */
    private static function shouldIgnoreFetch(
        string $path_type,
        string $expression_type,
        array $previous_path_types
    ) : bool {
        $el = \strlen($expression_type);

        if (substr($path_type, 0, $el + 7) === $expression_type . '-fetch-') {
            $fetch_nesting = 0;

            $previous_path_types = array_reverse($previous_path_types);

            foreach ($previous_path_types as $previous_path_type) {
                if ($previous_path_type === $expression_type . '-assignment') {
                    if ($fetch_nesting === 0) {
                        return false;
                    }

                    $fetch_nesting--;
                }

                if (substr($previous_path_type, 0, $el + 6) === $expression_type . '-fetch') {
                    $fetch_nesting++;
                }

                if (substr($previous_path_type, 0, $el + 12) === $expression_type . '-assignment-') {
                    if ($fetch_nesting > 0) {
                        $fetch_nesting--;
                        continue;
                    }

                    if (substr($previous_path_type, $el + 12) === substr($path_type, $el + 7)) {
                        return false;
                    }

                    return true;
                }
            }
        }

        return false;
    }

    /** @return array<Taintable> */
    private function getSpecializedSources(Taintable $source) : array
    {
        $generated_sources = [];

        if (isset($this->forward_edges[$source->id])) {
            return [$source];
        }

        if ($source->specialization_key && isset($this->specialized_calls[$source->specialization_key])) {
            $generated_source = clone $source;

            $generated_source->specialized_calls[$source->specialization_key]
                = $this->specialized_calls[$source->specialization_key];

            $generated_source->id = substr($source->id, 0, -strlen($source->specialization_key) - 1);

            $generated_sources[] = $generated_source;
        } elseif (isset($this->specializations[$source->id])) {
            foreach ($this->specializations[$source->id] as $specialization => $_) {
                if (!$source->specialized_calls || isset($source->specialized_calls[$specialization])) {
                    $new_source = clone $source;

                    $new_source->id = $source->id . '-' . $specialization;

                    $generated_sources[] = $new_source;
                }
            }
        } else {
            foreach ($source->specialized_calls as $key => $map) {
                if (isset($map[$source->id]) && isset($this->forward_edges[$source->id . '-' . $key])) {
                    $new_source = clone $source;

                    $new_source->id = $source->id . '-' . $key;

                    $generated_sources[] = $new_source;
                }
            }
        }

        return \array_filter(
            $generated_sources,
            function ($new_source) {
                return isset($this->forward_edges[$new_source->id]);
            }
        );
    }
}


1			<?php
2
3			namespace Psalm\Internal\Codebase;
4
5			use Psalm\CodeLocation;
6			use Psalm\Internal\Analyzer\StatementsAnalyzer;
7			use Psalm\Internal\Provider\ClassLikeStorageProvider;
8			use Psalm\Internal\Provider\FileReferenceProvider;
9			use Psalm\Internal\Provider\FileStorageProvider;
10			use Psalm\Internal\Taint\Path;
11			use Psalm\Internal\Taint\Sink;
12			use Psalm\Internal\Taint\Source;
13			use Psalm\Internal\Taint\TaintNode;
14			use Psalm\Internal\Taint\Taintable;
15			use Psalm\IssueBuffer;
16			use Psalm\Issue\TaintedInput;
17			use function array_merge;
18			use function array_merge_recursive;
19			use function strtolower;
20			use UnexpectedValueException;
21			use function count;
22			use function implode;
23			use function substr;
24			use function strlen;
25			use function array_intersect;
26			use function strpos;
27			use function array_reverse;
28
29			class Taint
30			{
31			/** @var array<string, Source> */
32			private $sources = [];
33
34			/** @var array<string, Taintable> */
35			private $nodes = [];
36
37			/** @var array<string, Sink> */
38			private $sinks = [];
39
40			/** @var array<string, array<string, Path>> */
41			private $forward_edges = [];
42
43			/** @var array<string, array<string, true>> */
44			private $specialized_calls = [];
45
46			/** @var array<string, array<string, true>> */
47			private $specializations = [];
48
49			public function addSource(Source $node) : void
50			{
51			$this->sources[$node->id] = $node;
52			}
53
54			public function addSink(Sink $node) : void
55			{
56			$this->sinks[$node->id] = $node;
57			// in the rare case the sink is the _next_ node, this is necessary
58			$this->nodes[$node->id] = $node;
59			}
60
61			public function addTaintNode(TaintNode $node) : void
62			{
63			$this->nodes[$node->id] = $node;
64
65			if ($node->unspecialized_id && $node->specialization_key) {
66			$this->specialized_calls[$node->specialization_key][$node->unspecialized_id] = true;
67			$this->specializations[$node->unspecialized_id][$node->specialization_key] = true;
68			}
69			}
70
71			/**
72			* @param array<string> $added_taints
73			* @param array<string> $removed_taints
74			*/
75			public function addPath(
76			Taintable $from,
77			Taintable $to,
78			string $path_type,
79			?array $added_taints = null,
80			?array $removed_taints = null
81			) : void {
82			$from_id = $from->id;
83			$to_id = $to->id;
84
85			if ($from_id === $to_id) {
86			return;
87			}
88
89			$this->forward_edges[$from_id][$to_id] = new Path($path_type, $added_taints, $removed_taints);
90			}
91
92			public function getPredecessorPath(Taintable $source) : string
93			{
94			$location_summary = '';
95
96			if ($source->code_location) {
97			$location_summary = $source->code_location->getShortSummary();
98			}
99
100			$source_descriptor = $source->label . ($location_summary ? ' (' . $location_summary . ')' : '');
101
102			$previous_source = $source->previous;
103
104			if ($previous_source) {
105			if ($previous_source === $source) {
106			return '';
107			}
108
109			return $this->getPredecessorPath($previous_source) . ' -> ' . $source_descriptor;
110			}
111
112			return $source_descriptor;
113			}
114
115			public function getSuccessorPath(Taintable $sink) : string
116			{
117			$location_summary = '';
118
119			if ($sink->code_location) {
120			$location_summary = $sink->code_location->getShortSummary();
121			}
122
123			$sink_descriptor = $sink->label . ($location_summary ? ' (' . $location_summary . ')' : '');
124
125			$next_sink = $sink->previous;
126
127			if ($next_sink) {
128			if ($next_sink === $sink) {
129			return '';
130			}
131
132			return $sink_descriptor . ' -> ' . $this->getSuccessorPath($next_sink);
133			}
134
135			return $sink_descriptor;
136			}
137
138			/**
139			* @return list<array{location: ?CodeLocation, label: string, entry_path_type: string}>
			0 ignored issues – show Documentation introduced 2020-06-30 17:30 UTC by Report Bug Copy Issue Report The doc-type `list<array{location:` could not be parsed: Expected "\|" or "end of type", but got "<" at position 4. (view supported doc-types) This check marks PHPDoc comments that could not be parsed by our parser. To see which comment annotations we can parse, please refer to our documentation on supported doc-types. Loading history...
140			*/
141			public function getIssueTrace(Taintable $source) : array
142			{
143			$previous_source = $source->previous;
144
145			$node = [
146			'location' => $source->code_location,
147			'label' => $source->label,
148			'entry_path_type' => \end($source->path_types) ?: ''
149			];
150
151			if ($previous_source) {
152			if ($previous_source === $source) {
153			return [];
154			}
155
156			return array_merge($this->getIssueTrace($previous_source), [$node]);
157			}
158
159			return [$node];
160			}
161
162			public function addThreadData(self $taint) : void
163			{
164			$this->sources += $taint->sources;
165			$this->sinks += $taint->sinks;
166			$this->nodes += $taint->nodes;
167			$this->specialized_calls += $taint->specialized_calls;
168
169			foreach ($taint->forward_edges as $key => $map) {
170			if (!isset($this->forward_edges[$key])) {
171			$this->forward_edges[$key] = $map;
172			} else {
173			$this->forward_edges[$key] += $map;
174			}
175			}
176
177			foreach ($taint->specializations as $key => $map) {
178			if (!isset($this->specializations[$key])) {
179			$this->specializations[$key] = $map;
180			} else {
181			$this->specializations[$key] += $map;
182			}
183			}
184			}
185
186			public function connectSinksAndSources() : void
187			{
188			$visited_source_ids = [];
189
190			$sources = $this->sources;
191			$sinks = $this->sinks;
192
193			for ($i = 0; count($sinks) && count($sources) && $i < 40; $i++) {
194			$new_sources = [];
195
196			foreach ($sources as $source) {
197			$source_taints = $source->taints;
198			\sort($source_taints);
199
200			$visited_source_ids[$source->id][implode(',', $source_taints)] = true;
201
202			$generated_sources = $this->getSpecializedSources($source);
203
204			foreach ($generated_sources as $generated_source) {
205			$new_sources = array_merge(
206			$new_sources,
207			$this->getChildNodes(
208			$generated_source,
209			$source_taints,
210			$sinks,
211			$visited_source_ids
212			)
213			);
214			}
215			}
216
217			$sources = $new_sources;
218			}
219			}
220
221			/**
222			* @param array<string> $source_taints
223			* @param array<Taintable> $sinks
224			* @return array<Taintable>
225			*/
226			private function getChildNodes(
227			Taintable $generated_source,
228			array $source_taints,
229			array $sinks,
230			array $visited_source_ids
231			) : array {
232			$new_sources = [];
233
234			foreach ($this->forward_edges[$generated_source->id] as $to_id => $path) {
235			$path_type = $path->type;
236			$added_taints = $path->unescaped_taints ?: [];
237			$removed_taints = $path->escaped_taints ?: [];
238
239			if (!isset($this->nodes[$to_id])) {
240			continue;
241			}
242
243			$new_taints = \array_unique(
244			\array_diff(
245			\array_merge($source_taints, $added_taints),
246			$removed_taints
247			)
248			);
249
250			\sort($new_taints);
251
252			$destination_node = $this->nodes[$to_id];
253
254			if (isset($visited_source_ids[$to_id][implode(',', $new_taints)])) {
255			continue;
256			}
257
258			if (self::shouldIgnoreFetch($path_type, 'array', $generated_source->path_types)) {
259			continue;
260			}
261
262			if (self::shouldIgnoreFetch($path_type, 'property', $generated_source->path_types)) {
263			continue;
264			}
265
266			if (isset($sinks[$to_id])) {
267			$matching_taints = array_intersect($sinks[$to_id]->taints, $new_taints);
268
269			if ($matching_taints && $generated_source->code_location) {
270			$config = \Psalm\Config::getInstance();
271
272			if ($sinks[$to_id]->code_location
273			&& $config->reportIssueInFile('TaintedInput', $sinks[$to_id]->code_location->file_path)
274			) {
275			$issue_location = $sinks[$to_id]->code_location;
276			} else {
277			$issue_location = $generated_source->code_location;
278			}
279
280			if (IssueBuffer::accepts(
281			new TaintedInput(
282			'Detected tainted ' . implode(', ', $matching_taints),
283			$issue_location,
284			$this->getIssueTrace($generated_source),
285			$this->getPredecessorPath($generated_source)
286			. ' -> ' . $this->getSuccessorPath($sinks[$to_id])
287			)
288			)) {
289			// fall through
290			}
291
292			continue;
293			}
294			}
295
296			$new_destination = clone $destination_node;
297			$new_destination->previous = $generated_source;
298			$new_destination->taints = $new_taints;
299			$new_destination->specialized_calls = $generated_source->specialized_calls;
300			$new_destination->path_types = array_merge($generated_source->path_types, [$path_type]);
301
302			$new_sources[$to_id] = $new_destination;
303			}
304
305			return $new_sources;
306			}
307
308			/** @param array<string> $previous_path_types */
309			private static function shouldIgnoreFetch(
310			string $path_type,
311			string $expression_type,
312			array $previous_path_types
313			) : bool {
314			$el = \strlen($expression_type);
315
316			if (substr($path_type, 0, $el + 7) === $expression_type . '-fetch-') {
317			$fetch_nesting = 0;
318
319			$previous_path_types = array_reverse($previous_path_types);
320
321			foreach ($previous_path_types as $previous_path_type) {
322			if ($previous_path_type === $expression_type . '-assignment') {
323			if ($fetch_nesting === 0) {
324			return false;
325			}
326
327			$fetch_nesting--;
328			}
329
330			if (substr($previous_path_type, 0, $el + 6) === $expression_type . '-fetch') {
331			$fetch_nesting++;
332			}
333
334			if (substr($previous_path_type, 0, $el + 12) === $expression_type . '-assignment-') {
335			if ($fetch_nesting > 0) {
336			$fetch_nesting--;
337			continue;
338			}
339
340			if (substr($previous_path_type, $el + 12) === substr($path_type, $el + 7)) {
341			return false;
342			}
343
344			return true;
345			}
346			}
347			}
348
349			return false;
350			}
351
352			/** @return array<Taintable> */
353			private function getSpecializedSources(Taintable $source) : array
354			{
355			$generated_sources = [];
356
357			if (isset($this->forward_edges[$source->id])) {
358			return [$source];
359			}
360
361			if ($source->specialization_key && isset($this->specialized_calls[$source->specialization_key])) {
362			$generated_source = clone $source;
363
364			$generated_source->specialized_calls[$source->specialization_key]
365			= $this->specialized_calls[$source->specialization_key];
366
367			$generated_source->id = substr($source->id, 0, -strlen($source->specialization_key) - 1);
368
369			$generated_sources[] = $generated_source;
370			} elseif (isset($this->specializations[$source->id])) {
371			foreach ($this->specializations[$source->id] as $specialization => $_) {
372			if (!$source->specialized_calls \|\| isset($source->specialized_calls[$specialization])) {
373			$new_source = clone $source;
374
375			$new_source->id = $source->id . '-' . $specialization;
376
377			$generated_sources[] = $new_source;
378			}
379			}
380			} else {
381			foreach ($source->specialized_calls as $key => $map) {
382			if (isset($map[$source->id]) && isset($this->forward_edges[$source->id . '-' . $key])) {
383			$new_source = clone $source;
384
385			$new_source->id = $source->id . '-' . $key;
386
387			$generated_sources[] = $new_source;
388			}
389			}
390			}
391
392			return \array_filter(
393			$generated_sources,
394			function ($new_source) {
395			return isset($this->forward_edges[$new_source->id]);
396			}
397			);
398			}
399			}
400

vimeo / psalm

Taint::getPredecessorPath() A last analyzed 2020-07-20 09:18 UTC

Complexity

Size

Duplication

Importance

Duplication Side-by-Side

Filter issues like

Taint::getPredecessorPath() A
last analyzed 2020-07-20 09:18 UTC